[알고리즘] DP - Knapsack Problem

Knapsack Problem (배낭 문제)

무게, 가치가 있는 물건들을 최대  K무게 만큼 담을 수 있는 가방에 넣을 때 최대로 넣은 수 있는 물건의 가치 구하기

---

출처 : https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

예제)

4개의 물건이 있다. 각 물건은 다음과 같은 무게와 가치를 가지는데, 배낭에는 최대  14만큼의 무게를 넣을 수 있다. 이 때 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구하라.

무게	가치
6	13
4	8
3	6
5	12

 

풀이)

다음 표를 1행에서 부터 채워 나가면 된다. 각 칸은 최대 무게가 1~7일 때 해당 물건을 넣을 경우 가질 수 있는 최대 가치가 된다. 즉 1행의 경우 최대 무게가 6,7일때 첫번째 물건을 넣을 수 있으므로 최대 가치가 13이 되고 나머지는 0이 된다.

	1	2	3	4	5	6	7
(6, 13)	0	0	0	0	0	13	13
(4, 8)	0	0	0	8	8	13	13
(3, 6)	0	0	6	8	8	13	14
(5, 12)	0	0	6	8	12	14	14

무게가 3이고 가치가 6인 물건을 넣는 경우를 살펴보자. 이 경우 해당 물건을 넣지 않는 다면 이전까지의 최대값인 13의 가치가 최대가 될 것이다. 하지만 (3, 6)인 물건을 포함시킬경우 4의 무게를 더 넣을 수 있기 때문에 이전 행의 4열에 해당하는 8만큼을 더 넣을 수 있다. 즉 6 + 8 = 14의 가치를 포함시킬 수 있다.

 

즉 i행의 j열을 채운다 하면 (i-1행 j열의 값)과 (이번 물건의 무게v + i-1행 j-w열 값)을 비교하여 둘 중 큰 값을 채우면 된다.

 

코드)

- c++

#include <iostream>
#include <algorithm>

using namespace std;

int N, K, w[100], v[100];
int dp[100][100001];

int main() {

	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> w[i] >> v[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= K; j++) {
			if (i == 0) {
				if (w[i] > j) dp[i][j] = 0;
				else dp[i][j] = v[i];
			}
			else {
				if (w[i] > j) dp[i][j] = dp[i - 1][j];
				else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
		}
	}

	cout << dp[N - 1][K] << endl;
	return 0;
}