[알고리즘] 배낭 문제(knapsack)

안녕하세요. 꿈꾸는 개발자입니다. 

이번에는 배낭(knapsack) 문제를 해결해 보려고 하는데요. 

배낭 문제는 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제입니다.(아래 위키 참조) 가방에 넣을 수 있는 최대 무게가 정해져 있고 넣을 수 있는 물건의 무게와 가치(값) 가 함께 문제에서 제시해 줍니다.

https://ko.wikipedia.org/wiki/배낭_문제

• 0-1 knapsack

가방에 넣을 수 있는 각 물건이 최대 1개만이 가능할 경우 입니다. 즉 종류별로 가방에 넣거나 넣지 않는 경우밖에 없으며, dp 의 루프는 오른쪽(큰 수) 에서 왼쪽(작은수)으로 진행이 됩니다.

[source]

/* 0 - 1 knapsack.cpp */

int n, W, dp [100];
int main (int argc, char* argv [])
{
    int i, j, w, v;
    scanf ("%d %d", &n, &w);
    for (i = 0; i < n; i++){
        scanf ("%d, %d", &w, &v);
        for (j = W ; j >= w; j--) {
            if (dp [j] < dp [j - w] + v)
                dp [j] = dp [j - w] + v;
        }
    }
    printf ("%d", dp[W]);
    return 0;   
}

• Unbounded Knapsack

물건의 개수를 제한 없이 가방에 넣을 수 있는 경우입니다. 즉 동일한 물건을 2개이상도 가방에 넣을 수 있는 경우로 0-1 knapsack 과는 다르게 loop  가 왼쪽에서 오른쪽으로 dp 가 진행이 됩니다.  

[source]

/* unbounded knapsack.cpp */
int n, W, dp [100];
int main (int argc, char* argv [])
{
    int i, j, w, v;
    scanf ("%d %d", &n, &w);
    for (i = 0; i < n; i++){
        scanf ("%d, %d", &w, &v);
        for (j = w ; j >= W; j--) {
            if (dp [j] < dp [j - w] + v)
                dp [j] = dp [j - w] + v;
        }
    }
    printf ("%d", dp[W]);
    return 0;   
}