[DP] 백준 12865 평범한 배낭 C++

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

12865번: 평범한 배낭

 

처음 읽고 쉬워 보여서 2시간넘게 고민 했는데 풀지못했다.. 결국 풀이를 찾아 봤는데 knapsack알고리즘 이라고 꽤나 유명한 알고리즘이다. 나중에 알고리즘 관한 부분은 따로 정리해서 업로드 할 예정.

내가 생각하지 못한 솔루션은 무게 남을 때 어떻게 최댓값을 찾을 것인가(코드상으로 dp[i-1][j-weight])부분이었다.

천천히 풀이해 보자

 

결국에 점화식을 어떻게 구하느냐 문제인데 내가 이해한 방식은

dp[i][j] = i번째 물건까지 검사했을 경우, 무게가 j일때 가치의 최대값

이런 방식으로 이해했다 문제에서 제공된 예시를 사용하면 첫 번째 물건을 검사할 경우

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
item1(6kg)	0	0	0	0	0	0	13	13

6키로 까지는 배낭에 넣을 수 없으므로 v최대값은 0이고 6키로 부터는 item1의 v인 13인 값을 갖게 된다. 이제 dp[i][j]에 item 1을 검사했을 때의 정보를 저장해 둔것이고 이제 다음 검사를 하면서 활용하면된다. 두번째 케이스의 경우

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
item1	0	0	0	0	0	0	13	13
item2(4kg)	0	0	0	0	8	8	13	13

이런식으로 배낭무게가 4키로가 되었을 때 item2를 넣을 수 있고 6키로가 되었을 때 이전에 저장해둔 정보를 활용해 최대값을 취하게 된다. 

이때 어떻게 최댓값을 취할 것이냐를 경우의 수를 나눠서 생각해봐야 한다.

1.  현재 item의 무게가 현재 최대 무게 보다 큰경우
2.  현재 item의 무게가 현재 최대 무게 보다 같거나 작은경우

1의 경우 배낭에 넣을 수 없다는 말이므로 이전케이스 까지 현재 검사하는 무게까지 v의 최대값을 구하놓았기 때문에 그대로 가져오면된다. (코드 상 dp[i-1][j])

2의 경우 현재 아이템을 넣을 수 있다는 말이므로 현재 아이템을 넣었을 때와 이전 케이스 까지 v의 최대값(dp[i-1][j]) 값 중 더 큰 값을 가지면 되는데 여기서 현재 아이템을 넣을 경우 현재 검사하는 무게에서 해당 무게를 빼줘야한다. 

예를 들어 현재 i = item4이고 현재 검사하려는 무게가 6인경우 item4의 무게는 5키로 이므로 item4를 넣었을 경우 이제 배낭에 넣을 수 있는 최대 무게는 1kg일 것이기 때문에!

 

 

 

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

int dp[101][100001];	// i번째 까지 검사했을 경우, 무게가 j일때 v의 최댓값
vector<pair<int,int>> item;	//first 는 무게, second 는 밸류 
int n, k;
int main() {
	cin >> n >> k;
	int a, b;
	item.push_back({ 0,0 });
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		item.push_back({ a,b });
	}

	for (int i = 1; i <= n; i++) {
		int weight = item[i].first; int val = item[i].second;
		for (int j = 0; j <= k; j++) {
			if (weight > j) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + val);
			}
		}
	}

	
	cout << dp[n][k] << endl;

}