Knapsack Problem，背包问题

有N个物品，分别有重量W和价格P两个属性，现在有一个包，可以容下最多T重量的物品，问将哪些物品放入包内，在不超重的情况下，物品价值总量最大。物品不可分割。

def knapsack(wlst, vlst, weight, value):
    assert len(wlst) == len(vlst)
    if weight < 0:
        return -1
    if not wlst or weight==0:
        return value
    a = knapsack(wlst[1:], vlst[1:], weight-wlst[0], value+vlst[0])
    b = knapsack(wlst[1:], vlst[1:], weight, value)
    return max(a,b)


T = 4
W = [4,5,1]
P = [1,2,3]
print(knapsack(W,P,T,0))  # 3

T = 3
W = [4,5,6]
P = [1,2,3]
print(knapsack(W,P,T,0))  # 0

T = 10
W = [1,2,3,4,5]
P = [5,4,3,2,1]
print(knapsack(W,P,T,0))  # 14

class knapsack():

    def __init__(self, wlst, vlst):
        self.length = len(wlst)
        assert self.length == len(vlst)
        self.wlst = wlst
        self.vlst = vlst

    def go(self, idx, weight, value):
        if weight < 0:
            return -1
        if idx==self.length or weight==0:
            return value
        a = self.go(idx+1, weight-self.wlst[idx], value+self.vlst[idx])
        b = self.go(idx+1, weight, value)
        return max(a,b)


T = 4
W = [4,5,1]
P = [1,2,3]
kp = knapsack(W,P)
print(kp.go(0,T,0))

T = 3
W = [4,5,6]
P = [1,2,3]
kp = knapsack(W,P)
print(kp.go(0,T,0))

T = 10
W = [1,2,3,4,5]
P = [5,4,3,2,1]
kp = knapsack(W,P)
print(kp.go(0,T,0))

Dynamic Programming

Top-Down

class knapsack():

    def __init__(self, wlst, vlst):
        self.length = len(wlst)
        assert self.length == len(vlst)
        self.wlst = wlst
        self.vlst = vlst
        self.rec = {}

    def go(self, idx, weight, value):
        if (idx,weight) in self.rec:
            return self.rec[idx,weight]
        if weight < 0:
            return -1
        if idx==self.length or weight==0:
            return value
        a = self.go(idx+1, weight-self.wlst[idx], value+self.vlst[idx])
        b = self.go(idx+1, weight, value)
        t = max(a,b)
        self.rec[idx,weight] = t
        return t

Bottom-Up

def knapsack(W,P,T):
    wlen = len(W)
    plen = len(P)
    assert wlen == plen
    rec = [[0]*(T+1) for _ in range(wlen+1)]
    for i,w in enumerate(W,1):
        for t in range(T+1):
            if t >= w:
                rec[i][t] = max(rec[i-1][t], rec[i-1][t-w]+P[i-1])
            else:
                rec[i][t] = rec[i-1][t]
    return rec[-1][-1]


T = 4
W = [4,5,1]
P = [1,2,3]
print(knapsack(W,P,T))  # 3

T = 3
W = [4,5,6]
P = [1,2,3]
print(knapsack(W,P,T))  # 0

T = 10
W = [1,2,3,4,5]
P = [5,4,3,2,1]
print(knapsack(W,P,T))  # 14

def knapsack(W,P,T):
    wlen = len(W)
    plen = len(P)
    assert wlen == plen
    rec = [0] * (T+1)
    for i,w in enumerate(W):
        c = rec[:]
        for t in range(T+1):
            if t >= w:
                rec[t] = max(c[t], c[t-w]+P[i])
            else:
                rec[t] = c[t]
    return rec[-1]

def knapsack(W,P,T):
    wlen = len(W)
    plen = len(P)
    assert wlen == plen
    rec = [0] * (T+1)
    for i,w in enumerate(W):
        for t in reversed(range(w,T+1)):
            rec[t] = max(rec[t], rec[t-w]+P[i])
    return rec[-1]

找出放入物品

def knapsack(W,P,T):
    wlen = len(W)
    plen = len(P)
    assert wlen == plen
    pmatrix = [['x']*wlen for _ in range(T+1)]  # x: no pick
    rec = [0] * (T+1)
    for i,w in enumerate(W):
        c = rec[:]
        for t in range(T+1):
            if t >= w:
                pw = c[t-w] + P[i]
                if c[t] > pw:
                    # pmatrix[t][i] = '<'  # <: previous, not this
                    rec[t] = c[t]
                else:
                    pmatrix[t][i] = 'y'  # y: pick this one
                    rec[t] = pw
            else:
                rec[t] = c[t]
    pick = []
    t = T
    i = wlen-1
    while not (t<0 or i<0):
        if pmatrix[t][i] == 'y':
            pick.append(i)
            i -= 1
            t -= W[i]
        # elif pmatrix[t][i] == '<':
        #    i -= 1
        else:
            i -= 1
    return rec[-1], pick[::-1]


T = 4
W = [4,5,1]
P = [1,2,3]
print(knapsack(W,P,T))

T = 3
W = [4,5,6]
P = [1,2,3]
print(knapsack(W,P,T))

T = 10
W = [1,2,3,4,5]
P = [5,4,3,2,1]
print(knapsack(W,P,T))

T = 10
W = [7,5,5,1]
P = [5,5,4,3]
print(knapsack(W,P,T))

(3, [2])
(0, [])
(14, [0, 1, 2, 3])
(9, [1, 2])

完全背包

完全背包问题与01背包问题不一样的地方在于，每件物品的数量无穷。这有点像找零钱问题，但约束条件和目标不一样。

本想先写DP递归版本，结果失败了，还没有想清楚如何保存子问题的结果......下面是Bottom-Up版本，与01背包问题的差异很小，但很关键：

def knapsack_complete_bu_old(W,P,T):
    wlen = len(W)
    plen = len(P)
    assert wlen == plen
    rec = [0] * (T+1)
    for i,w in enumerate(W):  # iterate items
        prev = rec[:]
        for t in range(T+1):  # iterate remain space
            if w <= t:
                n = t // w
                maxp = 0
                for j in range(n+1):
                    maxp = max(maxp, prev[t-w*j]+P[i]*j)
                rec[t] = maxp
            else:
                rec[t] = prev[t]
    return rec[-1]


T = 4
W = [4,5,1]
P = [1,2,3]
print(knapsack_complete_bu(W,P,T))

T = 3
W = [4,5,6]
P = [1,2,3]
print(knapsack_complete_bu(W,P,T))

T = 10
W = [1,2,3,4,5]
P = [5,4,3,2,1]
print(knapsack_complete_bu(W,P,T))

T = 10
W = [7,5,2,2]
P = [5,5,4,3]
print(knapsack_complete_bu(W,P,T))

def knapsack_complete_bu(W,P,T):
    wlen = len(W)
    plen = len(P)
    assert wlen == plen
    rec = [0] * (T+1)
    for i,w in enumerate(W):  # iterate items
        for t in range(w,T+1):  # iterate remain space
            rec[t] = max(rec[t], rec[t-w]+P[i])
    return rec[-1]