냅색 문제

KnapSack문제의 유형

크냅색
각 물건별로 value와 weight가 주어지고, 이 값에 맞추서 배낭에 물건을 넣어서 가장 가치가 높은 경우를 찾아내는 문제이다.

모든 경우의 수를 넣어본다

이는 Brute-Force로 푸는 방법이다. 다만 이는 2^n시간복잡도를 가지고, 아마 이렇게 푸는 일은 없을것이다.

가치가 높은것부터 넣는다

이는 그리디 방식으로 푸는것이다. 다만 항상 최적의 결과를 보장하지 못한다.

Fractional Knapsack이라고 불리는 물건을 잘라서 넣을 수 있는 문제는 이런 방식으로도 풀 수 있다.

문제

4 7
6 13
4 8
3 6
5 12

문제에서의 배낭에는 총 7의 무개를 버틸 수 있는 가방과 4개의 품목이 주어진다.

이때, dp를 다음과 같이 정의한다.
dp[i][j] = 처음부터 i번째 까지의 물건을 살펴보고, 배낭의 용량이 j일때 배낭에 들어가는 최대가치의 합이다.

• i번째 물건의 무개는 w[i]이고, 가치는 v[i]이다.
• 가방에 i번째 물건을 넣지 않았을때 가치의 최대합은 dp[i-1][j]이다.
• 만약 i번째 물건을 넣었다면, dp[i-1]j-w[i]] + v[i]가 그 최대값이 될 것이다.

예를 들어 dp[3][6] (3번째 물건까지 봄, 6이 배낭의 용량) 일때,

• MAX(dp[2][6], dp[2]6-w[3]] + v[3]) 이다.

전체 코드

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

int w[101];
int v[101];
int dp[101][100001];

int n, k;

int main() {
    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 = 1; j <= k; j++) {
            if (j - w[i] >= 0) { // 만약 무게한도 내라면 
                dp[i][j] = max(dp[i-1][j], dp[ i- 1][j - w[i]] + v[i]); // 점화식 
			} else{
                dp[i][j] = dp[i-1][j]; // 아니라면 이전값 
            }
        }
    }
    cout << dp[n][k];
}