백준 [12865] 평범한 배낭

유명한 배낭 문제

 

영문판 위키에 자세하게 나와있지만, 그림 설명은 없다.

 

en.wikipedia.org/wiki/Knapsack_problem

Knapsack problem - Wikipedia

 

캐시의 크기를 다음과 같이 초기화한다.

N : 물품의 수

K : 최대 무게

-> dp[N][K]

 

이제 배낭에 물건을 하나씩 넣어보면서, 이 물건이 있을 때가 최고의 가치를 가지는지 비교한다.

 

당연히, 입력으로 들어온 값은, 무게를 기준으로 오름차순 정렬한다.

 

예제의 입력을 기준으로 설명하자면 다음과 같다.

(3, 6) (4, 8) (5, 12) (6, 13)

 

처음 캐시의 상태는 다음과 같다. (입력만 받고, 계산은 아직 안 한 상태다)

초기 캐시 테이블

만약 N의 값이 K보다 큰 경우, N보다 가벼운 물건을 넣었을 때의 value를 저장한다.

즉, dp[i][j] = dp[i-1][j] 이다.

 

N=3인 경우, K가 3이 되기 전까지는 모두 N이 K보다 크므로, K<3 까지는

N=3보다 한 단계 작은 N=0을 넣었을 때 value를 저장해준다.

 

즉, 이런 캐시 테이블이 만들어진다.

N=3, K<3일 때 캐시 테이블

이제 K>=3부터는 N=3일 때의 value를 넣어줄 수 있다.

하지만, 무작정 넣을 수는 없고,

현재 무게 한도에서 해당 물건을 넣지 않았을 때의 가치와 (dp[i-1][j])

현재 무게 한도에서 해당 물건의 무게를 뺀 한도에서, 해당 물건을 넣지 않았을 때 가치 + 

원래 넣으려는 물건의 가치 (dp[i-1][j - N의 크기] + N의 가치)를 비교한다.

 

말로 설명하기 복잡하니 그림으로 설명하면 다음과 같다.

dp[i-1][j] = dp[0][3] = 0

dp[i-1][j-N의 크기] + N의 가치 = dp[0][0] + 6 이 되고,

N = 3을 넣었을 때의 가치가 더 크니, N = 3의 밸류인 6을 저장한다.

K>=N일 때 값의 비교

N=3일 때의 전체 캐시 테이블을 다음과 같다.

N=3, K>=3 일 때의 캐시 테이블

이제 N=4일 때를 보자.

마찬가지로, K<4까지는 이전 무게를 넣을 때의 value값을 가져와야한다.

하지만, K>=4일 땐 아까와 같이 비교를 해야 한다.

K=4일 때의 최종 테이블

 

이런 식으로 캐시 테이블을 완성하면 다음과 같은 캐시 테이블이 만들어진다.

최종 캐시 테이블

 

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	vector <pair <int, int>> bag;
	unsigned long long dp[102][100004] = { 0, };
	int N, K, W = 0, V = 0;
	int i, j, weightTemp, valueTemp;
	cin >> N >> K;
	for (i = 0; i < N; i++)
	{
		cin >> W >> V;
		bag.push_back(make_pair(W, V));
	}
	sort(bag.begin(), bag.end());
	for (i = 1; i <= N; i++)
	{
		for (j = 0; j <= K; j++)
		{
			weightTemp = bag[i - 1].first;
			valueTemp = bag[i - 1].second;
			if (weightTemp > j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weightTemp] + valueTemp);
		}
	}
	cout << dp[N][K];
	return 0;
}