[백준] 12865번 평범한 배낭

12865번: 평범한 배낭

주어진 무게들과 그에 따른 가치들을 pair로 벡터에 넣고 오름차순으로 정렬한다.

이차원 배열 DP를 만들어 0/1 Knapsack 원리로 구현한다.

 

평범한 배낭과 동전 문제와 비슷한 개념인데 차이점은

동전은 같은 동전을 여러 개 쓸 수 있다는 것이고

평범한 배낭은 이 물건을 가져가거나, 가져가지 않거나.

이 두가지 선택지밖에 없다는 것이다.

그래서 문제에 있는 예제로 표를 채워보면

 

가치	무게	1	2	3	4	5	6	7(K)
6	3	0	0	6	6	6	6	6
8	4
12	5
13	6

물건의 무게가 3이라 k가 1, 2일 땐 가져가지 못하므로 0이 되고

k가 3부터 7까지일 때는 이 물건을 가져갈 수 있으므로 가치 6으로 채워진다.

 

가치	무게	1	2	3	4	5	6	7(K)
6	3	0	0	6	6	6	6	6
8	4	0	0	6	8	8	8	14
12	5
13	6

물건의 무게가 4라서 k가 1, 2, 3일 땐 가져가지 못하므로 이전 값인 0, 0 6을 넣어주고

k가 4부터 6까지일 때는

 

(1) 이전에 k만큼 가져갔을 때 얻은 가치

(2) 이전에 k-4만큼 가져갔을 때 얻은 가치 + 무게 4를 가져갈 때 얻는 가치

 

이 두 가지 경우에서 더 큰 값을 넣어준다.

 

표시된 부분을 보면

 

(1) 이전에 7만큼 가져갔을 때 얻은 가치 = 6

(2) 이전에 3만큼 가져갔을 때 얻은 가치 + 무게 4를 가져갈 때 얻는 가치 =14

 

이렇게 되므로 더 큰 값인 14가 저장되는 것이다.

 

이런 식으로 표를 모두 완성시키면

가치	무게	1	2	3	4	5	6	7(K)
6	3	0	0	6	6	6	6	6
8	4	0	0	6	8	8	8	14
12	5	0	0	6	8	12	12	14
13	6	0	0	6	8	12	13	14

14가 답이 된다.

 

이대로 구현해주면 끝

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int N, K, W, V;
	cin >> N >> K;
	vector <pair<int, int>> v; //무게, 가치 순으로 집어넣는다
	int dp[101][100001] = { 0 };
	for (int n = 0; n < N; n++) {
		cin >> W >> V;
		v.push_back(make_pair(W, V));
	}
	sort(v.begin(), v.end());
	for (int i = 1; i <= K; i++) if (i >= v[0].first) dp[0][i] = v[0].second;
	for (int i = 1; i < v.size(); i++) {
		for (int j = 1; j <= K; j++) {
			if (j < v[i].first) dp[i][j] = dp[i - 1][j];
			else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second);
		}
	}
	cout << dp[N-1][K];
	return 0;
}