[c++/백준] 12865번: 평범한 배낭*

문제 링크

12865번: 평범한 배낭

풀이

dp를 이용하는 문제
무게가 k인 배낭을 쪼개서 푸는 문제.. 헷갈린다.

1. 입력받은 물건들을 무게 순으로 오름차순 정렬한다. 이 물건들의 인덱스는 1부터 시작될거임
2. dp를 초기화 하는데, 0행부터 n행까지는 해당 인덱스의 물건, 0열부터 k열까지는 배낭의 무게이다.
3. 0행이거나 0열일 경우에는 물건이 없거나, 가방이 없는 경우이므로 0으로 초기화 한다.
   3-1. 일단 현재 가방의 무게는 j이다. j 무게의 가방에 물건을 넣을 건데, 무게가 j보다 크면 가방에 못 넣으니까, j 무게 가방에 그 전 물건 넣었을 때 dp값. 그러니까 dp[i-1][j]값이 들어간다. 여기까지 점화식은 if j<wei dp[i][j] = dp[i-1][j]
   3-2. j 무게의 가방보다 현재 물건의 무게가 작으면 일단 들어가긴 할테니 현재 물건을 넣는 경우와 안 넣는 경우를 비교를 해주어야 한다.
   현재 물건을 넣는 경우) j-wei가방에 들어가는 전 물건까지의 dp값 + 현재 물건의 가치
   현재 물건을 안 넣는 경우) j가방에 들어가는 전 물건까지의 dp 값 (현재 물건을 안 넣을 거니까)
   즉, 점화식은 dp[i][j] = max(dp[i-1][j], dp[i-1][j-wei]+val)이 되겠다.
4. k무게 배낭의 n번째 보석까지 넣은 결과인 dp[n][k]를 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> object;
	for (int i = 0; i < n; i++)
	{
		int w, v;
		cin >> w >> v;
		object.push_back({ w,v });
	}
	object.push_back({ 0,0 });
	sort(object.begin(), object.end());

	vector<vector<int>> dp(n+1, vector<int>(k+1));
	for (int i = 0; i < dp.size(); i++)
	{
		int wei = object[i].first;
		int val = object[i].second;
		for (int j = 0; j < dp[i].size(); j++)
		{
			if (i==0 || j == 0)
			{
				dp[i][j] = 0;
			}
			else if (j < wei) // 물건의 무게가 가방 무게보다 무거울 경우
			{
				dp[i][j] = dp[i - 1][j];
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wei] + val);
			}
			//cout << dp[i][j] << " ";
		}
		//cout << endl;
	}

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