0/1 Knapsack 문제로 알려진 아주 아주 유명한 문제다. 이 문제에서는 각 물건들은 하나씩만 고를 수 있지만 물건 무한, 개수 제한 등등 여러가지 바리에이션이 있다. 동전 문제와도 겹치는 영역이 있다.
발상
완탐으로 생각해보면 각 물건들은 넣거나 빼거나 둘 중 하나의 상태를 가질 수 있으므로 이라는 끔찍한 시간 복잡도가 나온다. 어떻게 최적화할 수 있을까 ? 기저 사례부터 찾아보자. 넣은 물건이 하나도 없다면 답은 항상 0일 수 밖에 없으므로 기저 사례이다. 다음으로 새로운 물건을 집어넣는 경우를 생각해보자. 무게가 고 만족도가 인 번째 물건을 사용해 배낭 무게 를 만들 수 있는 무게는 이다. 그리고 그 때 얻을 수 있는 만족도 는 가 된다.
무게와 만족도를 오름차순으로 교차 순회하며 현재 물건을 넣은 만족도와 넣지 않은 만족도 중 큰 쪽을 골라 갱신해 나가면 최적값을 구할 수 있다. 왜냐하면 최적의 물건 조합의 부분 집합에 해당하는 모든 조합들은 그 무게 합의 최적일 수 밖에 없기 때문이다. 현재 물건을 추가하기 전의 무게에서 얻을 수 있는 최적의 만족도를 찾고 거기에 현재 물건을 더해 답을 갱신해 나가는 것이다.
주의할 점은 가방 무게가 음수일 수는 없기 때문에 만약 현재 넣을 수 있는 가방의 무게보다 더 무거운 물건이 주어졌을 경우 별도로 처리해 줘야 한다. 현재 물건을 집어넣을 수 없으니 이전 물건까지만 사용했을 때의 최적값을 그대로 넣어주면 된다.
점화식
예제
4 7
6 13
4 8
3 6
5 12
\ 무게
물건 0 0 0 0 0 0 13 13 // 무게 6, 만족도 13 짜리 물건을 집어넣은 경우
0 0 0 0 8 8 13 13 // 무게 4, 만족도 8짜리 물건을 집어넣은 경우
0 0 0 6 8 8 13 14 // 무게 3, 만족도 6짜리 물건을 집어넣은 경우 ( 무게 7에서
0 0 0 6 8 12 13 14
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;
struct ck {
int w, v;
};
int main() {
int n, m; cin >> n >> m; vector<vector<int>> dp(n + 1, vector<int>(m + 1)); vector<ck> arr(n + 1);
for (int i = 1; i <= n; i++) {
cin >> arr[i].w >> arr[i].v;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j < arr[i].w; j++) {
dp[i][j] = dp[i - 1][j];
}
for (int j = arr[i].w; j <= m; j++) {
int s1 = dp[i - 1][j - arr[i].w] + arr[i].v;
int s2 = dp[i - 1][j];
dp[i][j] = s1 > s2 ? s1 : s2;
}
}
cout << dp[n][m];
return 0;
}