BOJ 12865 평범한 배낭

이 문제는 완전 전형적인 Knapsack 문제이다! 

배낭의 무게가 w로 한정적일때, 가치가 모두 다른 보석들을 얼마만큼 넣어야 최적해인지 찾아야한다.

그렇다면 아래 그림을 통해 knapsack 문제를 더 살펴보자!

 

 

1) 현재 보석의 무게 > 배낭의 무게

이 경우는 해당 보석을 넣을 수 없으므로, 이전에 구해놓은 최적해 (이전 보석-현 배낭무게의 최적해)를 똑같이 복사한다.

 

2) 현재 보석의 무게 <= 배낭의 무게 

이 경우는 해당 보석을 넣을 수 있다. 하지만 이전에 구해놓은 최적해가 더 가치가 클 수 있으므로 비교해보자

즉 "현재 보석의 가치 + ( 현재 배낭의 무게에서 현재 보석의 무게를 뺀 경우의 최적해)"와 "이전 보석-현 배낭무게의 최적해" 를 비교하여 더 큰쪽을 저장한다.

 

 * 여기서 (현재 배낭의 무게에서 현재 보석의 무게를 뺀 경우의 최적해) 를 더하는 이유는 당연하다! 현재 보석을 배낭에 넣기 위해서는, 이전 보석들의 최적해 중에, 현재 보석의 무게가 빠진 경우를 봐야한다. 그래야만, 현재 보석을 배낭에 넣어도 배낭의 무게가 초과되지 않는다!

 

이렇게 무게 0부터 주어진 무게까지 계산을 한다.

 

이를 간단하게 점화식으로 표현한다면,

 

 

p[i][w] =  p[i-1] [w]  if ( wi > w)

    max(vali+p[i-1][w-wi] , p[i-1][w] else

 

i는 현재 보석, w는 현재 배낭의 무게  wi는 현재 보석의 무게, vali 는 현재 보석의 가치이다.

 

 

구현에서 더 추가되는 부분은, p 라는 2차원 배열이다. 2차원 배열을 선언하는 이유는 "해당 무게의 최적해" 들을 보석의 개수 별로 저장해야하기 때문이다 . 따라서 p[보석의개수][최대무게] 크기의 2차원 배열이 선언된다.

하지만 이게 끝이 아니다. p 배열의 맨 첫 행과 열은 모두 0으로 채워놔야 연산에 무리가 없다. (그러지 않으면 첫 보석을 계산할 때 매우 복잡해진다) 그러기 위해서 p[보석의 개수+1][최대무게+1] 로 바꾸어주자. 

그리고 각각 보석의 가치를 저장할 배열 val[보석의 개수] 와 보석의 무게를 저장할 배열 wt[보석의 개수]를 선언해준다.

그러면 0부터 보석의 개수 n 까지 루프를 돌고(변수 i) , 0부터 최대 무게 W까지 루프를 돌게 될 때 (변수 w) ,

현재 보석의 "가치"는  val[현재 보석을 가리키는 변수 i -1] 을 해주어야 하고, 현재 "보석의 무게" 는 wt[현재 보석을 가리키는 변수 i -1] (p가 보석의 개수 +1 이고, p의 0번째 행은 모두 0으로 채워졌으므로) 이 된다.

 

위의 쓴 점화식을 다시 코딩하면

 

if(i==0 || w==0) p[i][w]=0;
else if(wt[i-1] <= w) 
    p[i][w]=max(val[i-1]+p[i-1][w-wt[i-1]], p[i-1][w]);
else 
    p[i][w]=p[i-1][w];

이렇게 된다.

 

그리고 , 입력한 무게 W에서 가질 수 있는 최대의 보석의 개수는 p[n][w] 이 된다.

 

아래는 이를 응용하여 푼 백준 문제이다. 입력부분만 신경써준다면 일반 냅색문제와 다를게 하나도 없다!

#include <iostream>
using namespace std;
int p[101][100001];
int max(int n, int m) {
	if (n > m) return n;
	else return m;
}
int Knapsack_Problem(int wt[], int val[] ,int n, int W) {
	for (int i = 0; i <= n; i++) {
		for (int w = 0; w <= W; w++) {
			if (i == 0 || w == 0) p[i][w] = 0;
			else if (wt[i - 1] <= w) {
				p[i][w] = max(val[i - 1] + p[i - 1][w - wt[i - 1]], p[i - 1][w]);
			}
			else {
				p[i][w] = p[i - 1][w];
			}
		}
	}
	return p[n][W];
}


int main(void) {
	int n, k;
	int val[100];
	int wt[100];
	cin >> n;
	cin >> k;
	for (int i = 0; i < n; i++) {
		cin >> wt[i];
		cin >> val[i]; }
	cout << Knapsack_Problem(wt, val, n, k);
}