[BOJ] 12865 평범한 배낭

Table Of Contents

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

N

개의 물건이 주어지고, 각 물건은 무게

W

와 가치

V

를 가진다. 배낭에는 최대 무게

K

만큼만 담을 수 있다. 이런 상황에서 배낭에 담긴 물건의 가치를 최대로 만드는 문제이다.

점화식은 다음과 같이 세운다.

• dp[i][j]는 1~i번째 물건들만을 이용해서 무게가 j를 넘지 않도록 배낭을 채웠을 때, 가치의 합의 최대값이다.
• 우리는 N개의 물건을 이용해서 무게 K까지 채울 수 있으므로, dp[N][K]에 최종적으로 우리가 원하는 답이 저장된다.
• 우리가 현재 고려하는 i번째 물건의 무게는 w이고, 가치는 v이다.

1. i번째 물건을 배낭에 넣지 않는 경우
   • dp[i][j]는 1 ~ i번째 물건만을 이용하고 무게가 j를 넘지 않는 경우의 가치의 합의 최대값이다.
   • 따라서 i번째 물건을 이용하지 않는다면, dp[i][j]는 1 ~ i - 1번째 물건을 이용하고 무게가 j를 넘지 않는 경우의 가치의 합의 최대값과 같다.
   • 따라서 dp[i][j] = dp[i - 1][j]이다.
2. i번째 물건을 배낭에 넣는 경우
   • i번째 물건의 무게를 w, 가치를 v라고 하자.
   • 무게 w의 물건을 넣어서 배낭의 무게가 j가 되도록 하려면, 배낭의 무게가 j - w일 때 i번째 물건을 넣어야 한다. (j - w가 0보다 작은 경우에는 물건을 넣을 수 없다! 따로 예외처리를 해주자.)
   • 따라서 dp[i][j] = dp[i - 1][j - w] + v이다.
3. 최종적으로, dp[i][j]는 위 두 경우 중에 더 큰 가치가 들어가야 하므로 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)가 된다.

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

int N, K, W, V;
vector<vector<int> > dp;
// dp[갯수][무게]
// dp[N][K]

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> K;
	dp.resize(N + 1, vector<int>(K + 1, 0));

	for (int i = 1; i <= N; i++)
	{
		cin >> W >> V;

		for (int j = 1; j <= K; j++)
		{
			dp[i][j] = dp[i - 1][j];
			if (W <= j)
				dp[i][j] = max(dp[i][j], dp[i - 1][j - W] + V);
		}
	}

	cout << dp[N][K];

	return 0;
}