이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 35 번째 글 입니다.
목차
골드5 : 동적 계획법 문제이다.
생각
결국 무게 제약이 있는 문제이다. 나는 이 문제를 풀 때 감을 잡기 참어려웠는데, 무게에 제약이 있다는 점을 갖고 완전 탐색을 한다는 아이디어를 가지고 생각했다. 완전 탐색을 곧이곧대로 하려면 $O(n!)$ 의 시간 복잡도가 생겨 풀기 어렵다. 그렇기 때문에 이 문제는 다이나믹으로 접근한다.
다이나믹으로 접근하면, 작은 문제를 정의하고 이것이 큰 문제에 어떠한 영향을 주는 지를 확인해야 한다.
정의
dp[i][j] = i번째 물건까지 포함했을 때 j의 무게를 포함하는 가치의 최댓값
말이 좀 어렵다. 예시를 보자
4 7
6 13
4 8
3 6
5 12
현재 무게 : 6 현재 가치 : 13
1 2 3 4 5 6 7
0 0 0 0 0 13 13
현재 무게 : 4 현재 가치 : 8
1 2 3 4 5 6 7
0 0 0 8 8 13 13
현재 무게 : 3 현재 가치 : 6
1 2 3 4 5 6 7
0 0 6 8 8 13 14
현재 무게 : 5 현재 가치 : 12
1 2 3 4 5 6 7
0 0 6 8 12 13 14
14
새로운 아이템이 추가됨에 따라, 그 상태에서 가질 수 있는 가치의 최댓값을 가지고 있으면 문제는 해결된다.
점화식
dp[i][j] = max(dp[i][j], dp[i-1]j-a[i][0]]] + a[i][1];
위의 예시를 잘 보면, dp[4][7]을 업데이트 하기 위해서는 dp[3번째 무게까지 포함][4의 무게] + 6(3의 가치) 와 dp[3번째 무게까지 포함][7의 무게] 두개를 비교해야 한다. 즉, 8+6, 과 13을 비교한다.
잘 생각해보면, 이전 무게까지 포함했을 때 최댓값과, 새로 들어온 무게를 만들었을 때의 가치를 비교하면 되는 문제이다.
Code
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int N, K;
int a[101][2];
int dp[101][100001];
void print(int i){
cout << "현재 무게 : " << a[i][0] << " 현재 가치 : " << a[i][1] << '\n';
for (int j = 1; j <= K; j++) {
cout << setw(3) << j << " ";
}cout << '\n';
for (int j = 1; j <= K; j++) {
cout << setw(3) << dp[i][j] << " ";
}cout << '\n' << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
int w, v;
cin >> w >> v;
a[i][0] = w;
a[i][1] = v;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
// 만들고 싶은 무게에 지금 넣고 싶은 무게를 넣지 못하는 경우
if (j - a[i][0] < 0) {
// 이전 아이템까지 넣었던 최대 가치로 갖고 있는다
dp[i][j] = max(dp[i][j], dp[i-1][j]);
continue;
}
// 현재 만들고 싶은 무게에 지금 넣고 싶은 무게를 넣을 수 있다면
// 이전 아이템까지 넣었을 때 최대 가치를 가졌던 것과, 지금 넣고 싶은 무게를 넣었을 때
// 가치를 비교하여 최대 가치로 업데이트 해준다.
dp[i][j] = max(dp[i-1][j], dp[i-1][j-a[i][0]] + a[i][1]);
}
print(i);
}
// 최종적으로 N개의 짐까지 다 넣어보았을 때, 최대 가치가 얼마인지 찾는다.
cout << *max_element(dp[N], &dp[N][K+1]) << '\n';
//dp[i][j] = i번째 물건까지 포함했을 때 j의 무게를 만들었을 때 무게의 최댓값
// dp[i][j] = max(dp[i][j], dp[i-1][j-a[i].first] + a[i].second;
return 0;
}
공간 복잡도 감소
그런데, 지금 dp의 크기를 보면 100*100000 = 10000000이라 많은 메모리를 낭비하고 있다. dp[i]~dp[i+1] 과의 관계에서 값이 도출이 되기 때문에 이전 depth의 dp는 필요가 없다. 따라서 temp라는 배열에 이를 저장하고 그 저장한 배열에서 값을 따오면 공간 복잡도를 줄일 수 있다.
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int N, K;
int a[101][2];
int dp[100001];
int temp[100001];
void print(int i){
cout << "현재 무게 : " << a[i][0] << " 현재 가치 : " << a[i][1] << '\n';
for (int j = 1; j <= K; j++) {
cout << setw(3) << j << " ";
}cout << '\n';
for (int j = 1; j <= K; j++) {
cout << setw(3) << dp[j] << " ";
}cout << '\n' << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
int w, v;
cin >> w >> v;
a[i][0] = w;
a[i][1] = v;
}
for (int i = 1; i <= N; i++) {
memcpy(temp, dp, sizeof(dp));
for (int j = 1; j <= K; j++) {
if (j - a[i][0] < 0) dp[j] = max(dp[j], dp[j]);
else dp[j] = max(temp[j], temp[j-a[i][0]] + a[i][1]);
}
}
cout << *max_element(dp, dp+K+1) << '\n';
return 0;
}