背包问题动态规划

import sys
(M,N) = map(int, sys.stdin.readline().strip().split(',')) #容量，物品个数
w = map(int, sys.stdin.readline().strip().split(',')) #容量
v = map(int, sys.stdin.readline().strip().split(',')) #价值
f = (M+1)*[-1] #f[i] 表示容量还剩i的情况下所能承载的最大价值
#自底向上for k in range(M+1):    max = 0    for i in range(N):        sp = k-w[i]        if sp >=0:            if v[i] + f[sp] > max:                max = v[i] + f[sp]    print k,max    f[k] = maxprint f[M]sys.exit(0)"""
#自顶向下
def F(n):
    max = 0
    for i in range(N):
        sp = n - w[i]
        if sp >= 0:
            if f[sp] >= 0:
                t = v[i] + f[sp]
            else:
                t = v[i] + F(sp)
            if t>max:
                max=t
    f[n] = max
    return max
F(M)
max=0
for i in f:
    if i > max:
        max = i
print max