01背包問題_最大價值_二維.py

weight = [4,5,6,2,2]
value = [6,4,5,3,6]

W = 8 # 負重
num = len(value)
# or num = len(weight)

# ans = 15 # 最大價值 

#    0 1 2 3 4 5 6 7 8  
#  0 0 0 0 0 0 0 0 0 0
#  1 0
#  2 0 
#  3 0
#  4 0
#  5 0

#print([ [0] * (W+1) for _ in range(len(value)+1) ]  )
dp = [ [0] * (W+1) for _ in range(len(value)+1) ]
for i in range(1,num+1): # row 第幾個物品
    for j in range(1,W+1):
        # 要加物品 大於 現在負重 
        if weight[i-1] > j : 
            dp[i][j] = dp[i-1][j]
        # 要加物品 沒有大於 現在負重    
        else:
            dp[i][j] =  max(dp[i-1][j],dp[i-1][j-weight[i-1]]+value[i-1])

print(dp[num][W])