배낭(Knapsack) 알고리즘 (DP)

잘 정리된 곳 : http://blog.naver.com/mycho/220725983486

개요.

특정 용량의 배낭이 있고 n가지의 물건을 담을 수 있다. n가지의 물건은 각각 가치와 무게가 있으며 가치가 최대로 되도록 배낭에 담는 형식의 문제.

이 배낭 알고리즘에는 3종류가 있다고 한다.

1. 물건 당 물건의 수량이 1개밖에 없고 물건을 쪼갤 수도 없는 경우.(0-1 Knapsack problem)

2. 물건 당 물건의 수량이 여러개이고, 쪼갤 수 없는 경우.(Bounded Knapsack problem)

3. 물건의 갯수가 무한개이고, 쪼갤 수 없는 경우(Unbounded Knapsack problem)

1. 0-1 Knapsack problem.

물건 당 물건의 수량이 1개이고, 물건을 쪼갤 수 없는 경우.

- 기본적으로 물건을 가져가지 않는 경우와 가져가는 경우로 나누어서 둘중 최대값을 취하도록 함수를 작성함.

- 물건을 가져가지 않는경우 :

최대가치1 = getMaximum(남은용량, Item인덱스 + 1)

- 물건을 가져가는 경우 :

최대가치2 = getMaximum( 남은용량 - Item무게[i], item인덱스 + 1) + Item의가치[i]

아래는 배낭의 용량은 17, 물건의 갯수가 6개이고, 각각의 무게와 가치가 아래 리스트처럼 주어져있는 경우이다. 

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(1000000)
def getmax(capacity, index):
    ret = 0
    if index == n:
        return 0
    #아래는 가져가지 않는 경우.
    unselected = getmax(capacity, index+1)
    selected = 0
    #아래는 가져가는 경우.
    if capacity >= weight[index]:
        selected = getmax(capacity-weight[index], index+1) + value[index]
    #가져가지 않는 경우와 가져가는 경우중 최대값을 구해 리턴하면 된다.
    return max(unselected, selected)

weight = [4,2,6,4,2,10]
value = [7,10,6,7,5,4]
n = 6
capacity = 17
index = 0
print getmax(capacity, index)

2. Bounded Knapsack problem

물건 당 수량이 여러개이고, 쪼갤 수 없는 경우.

앞과 같은데 차이점이라면 갯수만큼 반복문을 돌려서 고른다는점.

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(1000000)
def getmax(capacity, index):
    ret = 0
    if index == n:
        return 0
    b = bound[index]
    for i in xrange(1,b+1):
        unselected = getmax(capacity, index+1)
        selected = 0
        if capacity >= weight[index]*i:
            selected = getmax(capacity-weight[index]*i, index+1) + value[index]*i
    return max(unselected, selected)

weight = [9,5,10,6,3]
value = [20,12,9,17,13]
bound = [2,2,3,1,1] #각각의 물건이 몇개있는지.
n = 5
capacity = 15
index = 0
print getmax(capacity, index)

3. Unbounded Knapsack problem

물건이 무한개이고 쪼갤수 없는 경우.

이건 이해하기 쉽다. 안 고르는 경우는 없으므로 없애주고, 모든 경우의 수에 대해서 결정한다.

# -*- encoding: cp949 -*-
import sys
sys.setrecursionlimit(1000000)
def getmax(capacity, index):
    ret = 0
    if capacity==0:
        return 0
    for i in xrange(n):
        if capacity >= weight[i]:
            ret = max(ret, getmax(capacity-weight[i], index+1)+value[i])
    return ret

weight = [10,6,7,2,5]
value = [18,5,11,12,16]
n = 5
capacity = 15
index = 0
print getmax(capacity, index)