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

# 0-1 Knapsack Problem 0-1 背包問題
'''
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 6, 6, 6, 6, 6]
[0, 0, 0, 0, 6, 6, 6, 6, 6]
[0, 0, 0, 0, 6, 6, 6, 6, 6]
[0, 0, 3, 3, 6, 6, 9, 9, 9]
[0, 0, 6, 6, 9, 9, 12, 12, 15]
ans: [0, 0, 6, 6, 9, 9, 12, 12, 15]
'''
weight = [4,5,6,2,2]
value = [6,4,5,3,6]

W = 8 # 負重
num = len(value)
# NUM = len(value) 

# ans = 15 # 最大價值 

# dp[目前重量] = 價值
## dp[限重] = 最大價值
dp = [0] * (W+1)
print(dp)


dp =[0] * (W+1) 
for i in range(1,num+1): # row 第幾個物品
    for j in range(W,weight[i-1]-1,-1):
        dp[j] = max(dp[j-weight[i-1]]+value[i-1],dp[j]) # 根據 現在負重 vs (現在負重-加入物品重)  
    print(dp)
print("ans:",dp)