배낭 문제(냅색 문제) - 2(분할 불가능한 냅색 문제)

분할이 불가능한 배낭문제를 0-1 배낭 문제라고 한다.

https://www.youtube.com/watch?v=A8nOpWRXQrs&t=3s 

* 동적 계획법으로 푸는법

 

n = 3
W = 30
w = [0,5,10,20]
p = [0, 50,60,140]


# 구하고자 하는것
# p[3][W] = p[3][30]

def knapsack2(i, W, w, p):
    if (i <= 0 or W <= 0):
        return 0
    if (w[i] > W):
        value = knapsack2(i - 1, W, w, p)
        print(i-1, W, value)
        return knapsack2(i - 1, W, w, p)
    else:
        left = knapsack2(i - 1, W, w, p)
        print(i - 1, W, left)
        right = knapsack2(i - 1, W - w[i], w, p)
        print(i - 1, W - w[i], right)
        return max(left, p[i] + right)

profit = knapsack2(len(w) -1, W, w, p)
print(profit)