a

[동적계획알고리즘] 0/1 배낭 문제 (knapsack)

박은성/ 2022. 4. 13. 20:54
반응형

동적 계획 알고리즘에서 5번째로 나온 알고리즘, 

배낭이 일정한 크기로 주어지고, 가방에 들어갈 아이템들이 있다. 각 아이템은 크기가 다양하고 각각의 가치를 갖고 있다. 배낭에 아이템을 담을 때, 아이템을 어떤 걸 넣어야 가장 가치와 크기가 최대인 배낭이 될 수 있을까?

 

배낭에 넣을 때, 아이템은 크기를 쪼갤 수 없다. 그래서 넣거나(1), 넣지 않거나(0) 해서 0 또는 1의 값만 갖게 된다. 

 

넣을지 말지를 결정하는 것이니, 모든 경우의 수를 세서 그 중 가치와 크기가 최적인 결과를 출력하면 어떨까? 만일 아이템이 n 개가 있다면, n개의 아이템이 넣/ 안넣, 이 두가지 경우의 수를 모두 세는 것이니 2의 n제곱의 수행시간이 소요된다. 그러니까 O(2^n)이다.

 

그런데 이건 시간이 너무 오래 걸린다. 동적계획으로 생각해 보자.

 

배열 A을 n개의 아이템을 담은 최적(가성비가 좋은) 부분집합이라고 가정하자. 

A가 n번째 아이템을 포함하지 않는다면, A는 n번째 아이템을 제외한 나머지 n-1개의 아이템들 중에서 최적으로 고른 부분집합과 같다.

나는 이 문장이 한 번 읽고 이해가 가지 않았으니 다시 읽어보길 바란다.

 

A가 n번째 아이템을 포함한다면, A에 속한 아이템들의 가치는 n-1개의 아이템들 중에서 최적으로 고른 아이템들의 가치와 n의 가치를 더한 것과 같다.

 

 

알고리즘)

Knapsack 
input : 배낭의 용량 C, n개의 아이템과 무게 w, 가치 v
output : K[n,C]
1. for i=0 to n K[i,0]=0 //배낭의 용량이 0일 때 -> 아무것도 담을 수 없다
2. for w=0 to C K[0,w]=0
3. for i=1 to n
	for w=1 to C
    	if(wi > w ) //i번째 아이템이 현재 w 보다 크다면	
        	K[i,w] = K[i-1, w] 
        else
        	K[i,w] = max{K[i-1,w], K[i-1,w-wi]+vi}
    return K[n,C]

그림으로 보면 이해가 쉽다. 

 

첫째 줄부터 보면, 무게가 5인 1번째 아이템을 넣으려고 한다. 배낭의 용량이 0 ~ 4인 배낭은 이 아이템을 담을 수 없다.

K[1, 1] = 0, K[1, 2] = 0, K[1, 3] = 0, K[1, 4] = 0

K[1, 5] = K[1, 6] = K[1, 7] = K[1, 8] = K[1, 9] = K[1, 10] = 10

그래서 결과는 5부터 10의 가치를 갖는 결과가 나온다.

 

 

이번엔 2번 아이템을 보자, 무게는 4이고 가치가 40이다. 마찬가지로 0~3 용량의 배낭에는 이 아이템이 담길 수 없다.

용량이 4인 배낭은 당연히 이 아이템을 넣게 된다.

그리고 용량이 5인 배낭의 경우, 1번 아이템을 넣을지 4번 아이템을 넣을지 가치가 최대가 되는 상황을 고려해야 한다. 그래서 max 함수를 통해 각각 반환된 가치값 중 큰 값을 가진 아이템을 담게 된다.

K[2,5] = max{K[i-1,w], K[i-1,w-wi ]+vi } 

        = max{K[2-1,5], K[2-1,5-4]+40}

        = max{K[1,5], K[1,1]+40}

        = max{10, 0+40} = 40

 

 

 

#include <iostream>
using namespace std;
struct Item{
	int w, v; // weight, value
};
int value[101][100001], n, k;
Item item[101];

int main(){
	cin >> n >> k; 
	for(int i =1; i<=n; i++){ // 아이템 배열 초기화
    	int w,v;
        cin>>w>> v;
        item[i] = {w, v};
    }
    for( int i=1; i<=n; i++){
    	for(int j =1; j<=k; j++){
        	int wi = item[i].w;
            int vi = item[i].v;
            
            //i 번째 아이템이 배낭 용량보다 크다면
            if( wi > j){
            	value[i][j] = value[i-1][j];
            }
            else {
            	value[i][j] = max(value[i-1][j], vi+value[i-1][j-wi]);
            }
            
         }
    }
    cout <<value[n][k];
    return 0;
 }
반응형