Knapsack Problem，背包问题

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 prep(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()
kp.prep(W,P)
print(kp.go(0,T,0))

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

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

class knapsack():

    def prep(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