알고리즘 이론 16강(2). 그리디 알고리즘 예제 - Knapsack Problem(배낭문제)

 

[The Knapsack Problem(배낭문제)]

: 유명한 그리디 알고리즘 문제중 하나.

배낭의 최대 용량이 W이고, 물건들의 집합 S의 물건들을 i라 한다. 이때, 각 i의 무게는 wi이고, 가치는 bi이다. 그러면 가방 안에 넣을수 있는 최대한의 가치를 얻을 수 있는 물건들의 집합은 무엇인가?

# 0-1 knapsack problem

  : 위 배낭 문제를 좀더 형식적으로 만든 문제. ("0-1" : 각 물건들은 전체를 가져가거나 아예 가져가지 못하는 조건 추가)

# fractional kanpsack problem

  : 아이템을 쪼개서 넣을수 있다.

 

 

[0-1 Knapsack Problem의 브루노 포스 해결법]

: O(2^n)의 시간 복잡도.. 모든 가능한 부분집합 사용

=> 동적 프로그래밍 방식으로 더 나은 풀이 유도 가능?

 

 

[0-1 Knapsack Problem의 알고리즘 선택법]

0. 주어진 문제

아이템 목록 : { {2,3}, {3,4}, {4,5}, {5,8}, {9,10} }    // {무게, 가치}

1. 부분문제 정의 : 우선 부분문제 식별 해봐야 한다.

Sk = {1, 2, ... k로 이름 붙은 아이템들중에서 최적해} 그러면, Sn이 부분문제 Sk에 포함되는가?    ex) W = 20일때,  S4 = {1,2,3,4}의 아이템중 최적해 => (2,3), (4,5), (5,8), (3,4) 가 최적 집합 S5 = {1,2,3,4,5}의 아이템중 최적해 => (2,3), (4,5), (5,8), (9,10) 가 최적 집합 => S4가 S5의 부분이 아니다. => 동적 프로그래밍은 부분문제의 최적해를 구해 기존문제의 최적해를 구하는 방식이기에 사용할 수가 없다..

2. 재귀적 풀이

: 기존 정보만으로는 동적 프로그래밍 방식을 위해 재귀식을 만들수 없다.

: 새로운 파라미터 w를 추가(각 아이템들의 부분집합의 정확한 무게를 나타태는 값)

 

 

 

[Knapsack Problem의 해결 알고리즘 선택 결론]

1) fractional problem은 그리디 알고리즘 방식으로 풀수 있다.

2) 0-1 problem은 그리디 알고리즘 방식으로 풀 수 없지만(전장의 돈세는 문제참고) 다이나믹 프로그래밍 방식으로 풀 수 있다.

 

 

 

[0-1 Knapsack Problem 해결식]

: 위에서 재귀식까지 다구해놨고, 이를 이용해 바텀-업 방식으로 바꿈

for w = 0 to W   B[0,w] = 0 for i = 0 to n   B[i,0] = 0   for w = 0 to W     if wi <= w       // 아이템 i가 최적 해결책의 부분집합에 포함되게된다.       if bi + B[i-1,w-wi] > B[i-1,w]         B[i,w] = bi + B[i-1, w-wi]       else         B[i,w] = B[i-1,w]     else       B[i,w] = B[i-1,w]

# 실행시간 : O(W) * O(W) = O(n*W)   // W는 아이템의 총 개수

 

 

[Fractional Knapsack Problem 해결식]

전략1. 가장 값어치 높은 물건부터 선택

전략2. vi/wi 기준을 가장 가치 높은 물건부터 선택 (가치/무게)

Fractional-Knapsack (W, v[n], w[n])   while w > 0   // 아이템 남아있는 동안, w : 배낭에 남은 공간     vi/wi의 가치가 가장 높은 아이템 선택     xi <- min (1, w/wi)     리스트에서 아이템 i 제거     w <- w-xiwi

# 실행시간 : 아이템이 전략기준으로 정렬 되어 있는 상태면 Θ(n), 아니면 Θ(nlogn)