[ 0/1 Knapsack] 배낭 냅색 알고리즘

냅색 문제(Knapsack Problem)는 물건들의 무게 w와 가치 v가 주어지고 배낭의 용량 c가 주어질때 배낭에 넣은 물건들의 가치의 합이 최대 몇인지 구하는 문제입니다. 0/1 냅색은 물건을 쪼개어 담을 수 없는 문제입니다.

12865번: 평범한 배낭

직관적으로 떠오르는 풀이는 특정 무게 _w에서 최대 가치의 합 dp[_w]을 구해가자! 입니다.

i번째 물건의 무게와 가치를 각각 arr[i][0], arr[i][1]이라고 정의하고 가겠습니다.

다만 _w가 어느 물건들의 무게 합인지 알 수 없기 때문에, 물건을 순서대로 집어 넣어보면서 시도해봐야 합니다.

i 번째 물건을 배낭에 넣었을때 무게가 cur_w 인 경우에서 가치의 최대값을 dp[cur_w]라고 정의한다면, 

dp[cur_w] = max(dp[cur_w], dp[cur_w - arr[i][0]] +arr[i][1]) 가 됩니다.

이때 cur_w 를 c부터 arr[i][0]까지 내림차순으로 반복해야하는데,

만약 arr[i][0]부터 c까지 오름차순으로 반복하게 되면 같은 물건이 중복되어 계산됩니다.

arr[i][0] 이 2이고 arr[i][1]이 큰 값 (1000000...)인 경우 0부터 진행한다면 dp[2]에서 arr[i][1]를 넣는 경우가 선택되고, dp[4]는 dp[4-arr[i][0]], 즉 이전에 arr[i][1]값이 들어간 dp[2]에 한번더 arr[i][1]의 값을 더 넣는 경우가 발생하는 예시로 생각하면 됩니다. (전 처음에 이것을 이해하는데 오래걸렸습니다.)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int n, k, arr[101][2], dp[100001] = { 0, };
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	for (int i = 0; i < n; i++) {
		for (int j = k; j >= arr[i][0]; j--) {
			dp[j] = max(dp[j], dp[j - arr[i][0]] + arr[i][1]);
		}
	}
	cout << dp[k];
}