배낭문제 Knapsack

배낭에 넣을 물건의 부분담기를 허락하지 않는다.그래서 그리디가 아닌, 동적 계획법을 통해 최적해를 구한다.시간 복잡도는 O(nC)

 

<Knapsack 슈도 코드>

입력: 배낭의 용량 C, n개의 물건과 각 물건 i의 무게 wi와 가치 vi, 단, i = 1, 2, ... n

출력: K[n,C]

1  for i = 0 to n    K[i, 0

] = 0   // 배낭의 용량이 0일 때

2  for w = 0 to C  K[0,w] = 0  // 물건 0이란 어떤 물건도 배낭에 담기 위해 고려하지 않았을 때

3  for i = 1 to n {

4    for w = 1 to C {       // w는 배낭의 (임시)용량이고, 마지막에는 w=C가 되어 배낭의 용량이 된다.

5           if( wj > w )       // 물건 i의 무게가 임시 배낭의 용량을 초과하면

6              K[i,w] = K[i-1,w]

7           else

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

        }

     }

9 return K[n,C] 

 

---

<배낭문제 문제 풀어보기>