[백준]12865 평범한 배낭 c++

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

12865번: 평범한 배낭

 

[접근 방법]

배낭 문제는 knapsack 알고리즘을 통해푼다.

 

예제를 바탕으로

n =4, k =7,

6 13

4 8

3 6

5 12 // 무게, 가치 순서

열 인덱스 : 배낭의 최대 무게

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

먼저 6kg를 기준으로 배낭에 넣어본다. 6kg부터 가치가 생김.

	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)
5 (12)

4kg를 배낭에 넣어본다.

4kg와 6kg 아이템만 있다고 가정했을 때 배낭에 담을 수 있는 최대 가치는 13

	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	8	8+6 (14)
5 (12)

3kg을 배낭에 넣어본다.

배낭 최대 무게가 7kg일 때 4kg와 3kg 아이템이 들어갈 경우 최대 가치를 얻을 수 있다.

	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	8	8+6 (14)
5 (12)	0	0	6	8	12	12	14

5kg을 배낭에 넣어본다.

배낭 최대 무게가 5kg일 때 5kg아이템이 들어갈 때 최대 가치를 얻을 수 있지만

7kg일 때는 3kg+4kg 가치가 더 크다.

 

이러한 방법을 식으로 표현하면

dp[i][j]= max(dp[i-1][j] , dp[i-1][j-item.무게] + item.가치)

 

[코드]

#include <iostream>
#include <algorithm>

using namespace std;

int items[101][2];
int dp[101][100001] = { 0, };

int main() {
	int n, k, w, v;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> w >> v;
		items[i][0] = w; 
		items[i][1] = v;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= k; j++)
		{
			if (j >= items[i][0]) {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i][0]] + items[i][1]);
			}
			else
				dp[i][j] = dp[i-1][j];
		}
	}
	cout << dp[n][k];

	return 0;

}