[2][Knapsack][0/1 배낭 문제] (0/1Knapsack Problem)

배낭 문제

배낭문제는 n개의물건이 있고 각각 무게와 가치가 주어질때, 물건을 m이하의 무게로 담을때 가능한 최대 가치를 구하는 문제이다.

 

이 배낭 문제는 크게 3가지로 분류된다.

 

• 배낭 빈틈없이 채우기 문제 ( Fractional Knapsack Problem)
• 0/1 배낭 문제 (0/1 Knapsack Problem)
• 개수제한 없는 0/1 배낭 문제 (Unbounded Knapsack Problem)

이 중 0/1 배낭 문제 (0/1 knapsack problem) 에 대해 알아보자.

 

---

0/1 배낭 문제 ( 0/1 Knapsack Problem)

0/1배낭 문제는 최대 가방무게 이하로 물건을 담을때 가치가 최대로 최게 담아야하는데

 

단, 물건을 일부만 담을 수 없고 담거나 담지 않거나 둘중 한가지를 택해야한다.

 

첫번째로 생각해볼 수 있는 방법은 가치 순으로 내림차순으로 정렬해서 가치가 큰것부터 먼저 담는 방법이다.

 

그러나 아래의 예처럼 아무리 가치 높은 물건을 먼저담아도 그 후에 가치가 작은 물건 여러개를 고름으로써 더 큰 가치가 나올수도있다.

 

따라서 이방법으로는 안될것이다.

 

 

 

 

두번째로 생각해볼수 있는 방법은 무게가 가벼운 순서대로 오름차순해서 가벼운것을 먼저 넣는 전략이다.

 

그러나 아래 예처럼 처음에 가벼운것들을 먼저 넣는것보다 나중에 무거운것 하나를 넣는것이 더 큰 가치가 나올수도 있다.

 

이 방법또한 사용하지 못한다.

 

 

 

그렇다면 fractional knapsack에서 사용했던 방법처럼 가치/무게 값으로 내림차순해서 무게대비 가치의 효율이 높은것 먼저 넣으면 되지않을까.

 

아쉽게도 이방법으로도 불가능하다.

 

아래의 경우처럼 가장 효율이 좋은 물건 하나보다 효율이 좀 떨어지는 물건 두개를 고르는것이 더큰 가치가 만들어질수 있다.

 

 

 

이 문제를 풀기위해서는 동적계획법을 이용해서 풀어야한다.

 

각 상품에 대해 담을지 말지 두가지 경우가 있으므로 총 n개의 상품을 가방에 넣을때 총 경우의 수는 2^n인데

 

동적계획법을 이용해 불필요한 반복을 줄여서 시간복잡도를 줄일수 있다.

 

#include <stdio.h>

#define INF 987654321;

typedef struct KNAPSACK{
    int w,v; // 각각의 상품에 대한 무게,가치를 저장하는 구조체
}Knapsack;

Knapsack ks[101]; // 입력으로 상품이 최대 100개 들어온다고 가정

int ddp(int now, int weight);
int maximum(int x, int y);

int dp[101][100001] = {0};
int n,k; // n : 전체상품의 개수, k : 담을 수 있는 최대 상품 무게

int main(){
    int i;
    scanf("%d %d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d %d",&ks[i].w,&ks[i].v);
    }
    printf("%d",ddp(0,0)); // 시작할때 인덱스는 0이고 무게는 0으로 시작

}

int ddp(int now, int weight){ 
// now : 담을지말지 고민하고 있는 상품의 인덱스
// weight : now번째 이전까지 담은 상품들의 총 무게

    int tmp1,tmp2,ans;
    if(weight > k){ // 만약 현재까지 담은 상품들 무게가 최대무게를 초과한다면 매우 작은수를 내보낸다(약 -9억)
        return (-1) * INF;
    }
    if(now == n){ // 만약 모든 상품들을 순회했다면 정상적으로 0을 리턴해서 최종 합을 리턴시킨다.
        return 0;
    }
    if(dp[now][weight] != 0){ 
    // 만약 현재 now번째 물건을 담기 전까지 weight만큼 가방을 채웠었고
    //현재 now번째 물건을 채워야하는 상황이 이전에 있었다면 이후로는 결과값이 동일하므로 저장된 값을 가져온다 
        return dp[now][weight];
    }
    tmp1 = ks[now].v + ddp(now+1,weight+ks[now].w); // 현재 물건을 가방에 담는 케이스
    tmp2 = ddp(now+1,weight); // 현재 물건을 담지 않고 넘어가는 케이스

    ans = maximum(tmp1, tmp2); // 위 두케이스 중 큰 케이스가 최종값이 된다.
    dp[now][weight] = ans; 
    // 현재 weight의 무게까지 채웠고 now를 담을지 말지 고민하는 경우의 최대값을 
    // 나중에 재방문 했을때 불필요한 중복을 없애기 위해 저장해둔다.
    return ans;
}

int maximum(int x, int y){
    return x > y ? x : y;
}