728x90
https://www.acmicpc.net/problem/12865
냅색 알고리즘을 이용하는 문제였다....
근데 처음에 생각하지 못하고 삽질삽질하다가,,, 냅색알고리즘도 야매로 구현하다가,,,
수많은 삽질끝에 해결했다!
작년 알고리즘 수업때 배운 기억이 있는데,,, 잠깐 언급하고 지나갔나? 자료를 찾을 수 없었다.
이 기회에 DP공부를 좀 확실히 해야겠다.
냅색 알고리즘의 기본문제?같은 느낌이다.
알고만 있으면 바로 풀 수 있는!!
그래서,,,,
따로 정리해서 링크로 추가해두려고 한다ㅎ
>>> <<<
1. 메모리초과
=> 냅색 알고리즘을 생각하지 못하고, 완전탐색으로 풀었다!
더보기
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int n, k;
vector<pair<int, int>> weight_values;
vector<vector<int>> how_bags;
void choose(int index, vector<int> now_bags) {
if (index == n) {
how_bags.push_back(now_bags);
return;
}
choose(index + 1, now_bags);
now_bags.push_back(index);
choose(index + 1, now_bags);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
weight_values.push_back({ a, b });
}
choose(0, {});
int result = INT_MIN;
for (int i = 0; i < how_bags.size(); i++) {
vector<int> now_bags = how_bags[i];
int weight_sum = 0;
int value_sum = 0;
for (int j = 0; j < now_bags.size(); j++) {
weight_sum += weight_values[now_bags[j]].first;
value_sum += weight_values[now_bags[j]].second;
}
if (weight_sum <= k) {
result = max(result, value_sum);
}
}
if (result == INT_MIN) {
result = 0;
}
cout << result;
return 0;
}
2. 냅색 알고리즘 도입 => 86%를 넘지 못함,,
더보기
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int n, k;
vector<pair<int, int>> weight_values;
vector<vector<int>> dp;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first < b.first;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
dp = vector<vector<int>>(n, vector<int>(k, 0));
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
weight_values.push_back({ a, b });
}
sort(weight_values.begin(), weight_values.end(), cmp);
// 확인할 물건의 index : 0
for (int i = 0; i < k; i++) {
if (i + 1 >= weight_values[0].first) {
dp[0][i] = weight_values[0].second;
}
}
for (int j = 0; j < k; j++) {
if (j + 1 > weight_values[0].first) {
dp[0][j] = weight_values[0].second;
}
for (int i = 1; i < n; i++) {
// 무게 : j+1까지
// 확인할 물건 : i
if (j + 1 > weight_values[i].first) {
// 넣을 수 있음
dp[i][j] = max(dp[i - 1][j], dp[i-1][j - weight_values[i].first] + weight_values[i].second);
}
else {
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[n - 1][k - 1];
return 0;
}
j부터 반복을 시작하는 이유는, 특정 무게에서 물건을 하나씩 넣어보는 동작을 해야하기 때문이었다.
(i번째 물건을 넣기 위해, 그 이전 i-1번째 물건까지의 기록을 바탕으로 추가해야 하므로)
=> 반복이 반대로 들어가면, 개수에 맞게 무개를 증가시킨다 == 내 머릿속으로는 반복이 3번들어가야 할것같았다..
이렇게 보니, 애초에 dp를 선언할 때 [물건개수][무게] 가 아니라 [무게][물건개수]로 선언했으면 더 효율적이었을것같다..만 통과했으니까/.ㅎㅎ
이 코드가 통과하지 못한이유는...
3. 무게비교
더보기
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int n, k;
vector<pair<int, int>> weight_values;
vector<vector<int>> dp;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.first < b.first;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
dp = vector<vector<int>>(n+1, vector<int>(k+1, 0));
weight_values.push_back({ 0, 0 });
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
weight_values.push_back({ a, b });
}
//sort(weight_values.begin(), weight_values.end(), cmp);
for (int j = 0; j <= k; j++) {
for (int i = 1; i <= n; i++) {
// 무게 : j까지
// 확인할 물건 : i
if (j >= weight_values[i].first) {
// 넣을 수 있음
dp[i][j] = max(dp[i - 1][j], dp[i-1][j - weight_values[i].first] + weight_values[i].second);
}
else {
dp[i][j] = dp[i - 1][j];
}
//cout << i << ", "<<j << " : "<< dp[i][j] << endl;
}
}
cout << dp[n][k];
return 0;
}
무게 비교할 때 등호를 넣어줘야했다!.....
"이하"일 때 담을 수 있으니까.. 딱 맞을때도 담을수 있다.ㅎㅎ.ㅎ.ㅎ...
728x90
'코테준비 > 하루한개도전~' 카테고리의 다른 글
8/4 TIL : DP (0) | 2024.08.04 |
---|---|
99클럽 코테 스터디 11일차 TIL : 숫자 카드2 (0) | 2024.08.04 |
8/3 TIL : Backtracking & BFS (0) | 2024.08.04 |
99클럽 코테 스터디 10일차 TIL : 숫자 카드 (0) | 2024.08.03 |
8/1 TIL : Backtracking (0) | 2024.08.02 |