DynamicProgramming

01knapsack.py

va = '51 94 66 55 81 99 79 12 14 32 36 88 65 79 62 37 47 13 93 77 100 26 44 66 73 71 74 27 6 43 16 50 7 65 3 58 7 90 99 60 84 54 68 45 28 5 43 77 47 68 9 83 66 20 84 67 4 70 90 80 11 72 54 63 9 91 43 44 36 89 60 92 70 13 66 43 45 20 32 22 61 94 25 79 27'
wt = '6 89 12 23 22 72 2 25 47 40 51 93 15 49 85 43 88 75 96 72 72 26 90 46 17 69 74 73 7 25 35 27 7 19 77 53 11 21 20 32 39 45 24 19 54 94 85 9 38 19 40 37 40 53 62 32 47 20 19 51 90 5 89 50 68 63 59 8 64 16 24 51 13 37 76 63 68 32 12 18 12 60 45 39 64'
N = len(wt.split()) ## 物品数量
wt = list(map(int, wt.split())) # 重量
va = list(map(int, va.split())) # 价值
V = 50 # 背包最大容量
F = [0 for i in range(V+1)]
for i in range(N):
    for v in range(V, 0, -1):
        if wt[i] <= v:
            F[v] = max(F[v], F[ v-wt[i] ]+ va[i])

print(F[-1])