Knapsack 알고리즘 (배낭싸기 알고리즘 )

" 당신이 보석을 털러 보석점에 침입했다.

각각의 보석 n개가 있고 보석마다 무게와 가치가 다르다.

당신의 가방에 담을 수 있는 무게에 한계가 있을 때,

당신이 가져나올 수 있는 보석들의 가치 합은 최대 얼마인가. "

무게와 가치가 따로 있고 가져갈 수 있는 최대 가치를 묻는 문제들,

이런 류의 문제는 Knapsack 알고리즘으로 풀 수 있다.

모든 경우를 다 따져보는 알고리즘, 즉 Greedy 알고리즘으로 이 문제를 해결할 수 있다.

하지만 시간복잡도가 2^n이기 때문에 n이 커지면 시간이 오래걸린다.

그리고 항상 최적의 답을 낼 거라는 보장이 없다. Greedy 알고리즘은.

그렇기에 Knapsack 문제는 다이나믹 프로그래밍으로 풀어야한다.

w[i]가 i번째 보석의 무게, v[i]가 i번째 보석의 가치, 

D[i][j]가 i번째 보석까지 탐색한 현 상태, j만큼의 무게를 가져갔을 때 획득한 가치의 최대치라고 하자.

D[i][j]는 두가지 경우가 있다.

- 1. i번째 보석을 가져간 경우

이 경우는 D[i][j] = D[i-1][j-w[i]] + v[i]라 할 수 있다.

i-1까지 보석을 탐색한 경우의 무게는 j에서 i번째 보석의 무게를 뺸 것이기 때문.

- 2. i번쨰 보석을 가져가지 않은 경우

i-1까지 탐색한 경우에서 i번째 보석을 가져가지 않았기 떄문에 무게도 그대로

D[i][j] = D[i-1][j]가 된다.

i를 첫번째 보석부터 n번째 보석까지,

   

      j를 0kg부터 k(배낭이 담을 수 있는 최대 무게)까지 

         D[i][j] = max(D[i][j], D[i-1][j-w[i]] + v[i])

이것이 Knapsack 알고리즘이다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int d[101][100001];
int w[101];
int v[101];
 
int main() {
    
    //freopen("Text.txt", "r", stdin);
 
    int n, k;
 
    cin >> n >> k;
 
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            d[i][j] = d[i - 1][j];
            if (j - w[i] >= 0) {
                d[i][j] = max(d[i][j], d[i - 1][j - w[i]] + v[i]);
            }
        }
    }
 
    cout << d[n][k] << endl;
 
}