https://www.acmicpc.net/problem/12865
풀이 아이디어)
물건에 번호를 붙여서 해당 물건이 들어갔을때 특정 무게시점에서의 가치를 구한다.
result[i][j] 배열을 사용하며 i번물건을 넣고자 할때 사용가능 무게가 j인시점에서의 가치를 저장한다.
0번은 비워두고 1번부터 사용한다.
설명)
사람의 사고순서가 아니라 메모리에 그냥 기록하면서 지나가는 방식이라 설명을 몇번이나 쓰고 지워봤지만 내가봐도 이해못할 설명이고 설명이 너무 더럽다.
항상 DP문제는 설명 백날 보는것보다 점화식 한번 보는게 이해가 훨씬 빠른것 같다.
점화식은 아래와 같다.
if (j >= w) result[i][j] = max(result[i - 1][j], result[i - 1][j - w] + v); // 들어갈수 있다면
else result[i][j] = result[i - 1][j]; // 들어갈 수 없다면
결국 무게 j인 시점에 i번 물건을 넣는것보다 i - 1번 물건이 들어가는게 가치가 더 크다면 그 값을,
i - 1번 물건을 빼고 i번 물건을 넣는게 가치가 더 크다면 i - 1번물건이 안들어간 시점에서 i의 무게와 가치를 더해주면 된다.
그리고 만약 무게 4에 가치8인 물건이 들어가있다면 무게5인 시점에 무게1인 물건이 들어가지 않고서야 무게5 시점에도 가치는 8이다.
또한 4번물건이 무게가 5라서 j가 4라면 들어갈 수 없는 상황인데 이미 3번물건이 들어가있다면 3번물건이라도 들어가있는것이 더 가치가 높다. 그러므로 현재 물건이 들어갈수 없는 상황이면 이전물건이 들어가있는 가치가 더 높다.
이점만 이해하면 점화식으로 이해하는게 더 빠르다.
4 7
6 13
4 8
3 6
5 12| dp[i][j] | [ ][1] | [ ][2] | [ ][3] | [ ][4] | [ ][5] | [ ][6] | [ ][7] |
| [0][ ] | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| [1][ ] | 0 | 0 | 0 | 0 | 0 | 13 | 13 |
| [2][ ] | 0 | 0 | 0 | 8 | 8 | 13 | 13 |
| [3][ ] | 0 | 0 | 6 | 8 | 8 | 13 | 14 |
| [4][ ] | 0 | 0 | 6 | 8 | 12 | 13 | 14 |
정답코드)
벡터 사용시
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(NULL);
int N, K;
cin >> N >> K;
vector<pair<int, int>> thing(N + 1);
int W, V;
for (int i = 1; i < N + 1; i++) {
cin >> W >> V;
thing[i].first = W;
thing[i].second = V;
}
vector<vector<int>> result(N + 1, vector<int>(K + 1, 0));
for (int i = 1; i < N + 1; i++) {
for (int j = 0; j < K + 1; j++) {
int w = thing[i].first;
int v = thing[i].second;
if (j >= w) result[i][j] = max(result[i - 1][j], result[i - 1][j - w] + v);
else result[i][j] = result[i - 1][j];
}
}
cout << result[N][K];
return 0;
}
배열사용시
#include<iostream>
#include<algorithm>
using namespace std;
int N, K;
int DP[101][100001];
int W[101];
int V[101];
// 점화식 max(DP[i-1][j], DP[i-1][j-W[i]])
int main()
{
cin >> N >> K;
for (int i = 1; i <= N; i++)
cin >> W[i] >> V[i];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= K; j++)
{
if (j - W[i] >= 0) DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W[i]] + V[i]);
else DP[i][j] = DP[i - 1][j];
}
}
cout << DP[N][K];
}
※ 참고문헌