問題描述：
給定 n 件物品，物品的重量為 w[i]，物品的價值為 v[i]?，F(xiàn)挑選物品放入背包中，假定背包能承受的大重量為 c，問應(yīng)該如何選擇裝入背包中的物品，使得裝入背包中物品的總價值大？
首先輸入共n個物品，一個容量為v的背包，n和v沒有協(xié)同關(guān)系，只是制約關(guān)系
再輸入[各物品重量,各物品價值]
分別存入重量數(shù)組與價值數(shù)組
本題以n，v=4，5 ，輸入（1，2）（2，4）（3，4）（4，5）為例
重慶分公司
重慶分公司
N,V = map(int,input().split())
weight = []
val = []
for _ in range(N):
wi,vi = map(int,input().split())
weight.append(wi)
val.append(vi)weight=[1,2,3,4]
value = [ 2,4,4,5]
dp = [ [0]*(V+1) for _ in range(N+1) ]
因為存在【沒有物品，但有容量】與【有物品，容量不夠】的情況，所以保留0數(shù)組
又因需要到達(dá)n,則range(N+1)
則五行六列
行：前4件物品
列：容量為1到5的書包
{ weight[i] , value[i] }與dp之間的關(guān)系：
dp通過 【i-1，{ 減weight[i] } + value[i]} 】 到達(dá) 下一個dp
for i in range(1,N+1):
for w in range(1,V+1):
if w為什么是i-1呢？因為保留0的原因，導(dǎo)致i相比 與 相對應(yīng)的 value大1，
總代碼N,V = map(int,input().split())
weight = []
val = []
for _ in range(N):
wi,vi = map(int,input().split())
weight.append(wi)
val.append(vi)
dp = [[0]*(V+1) for _ in range(N+1)] # (N+1)*(V+1)
for i in range(N):
dp[i][0]=0
for i in range(1,N+1):
for w in range(1,V+1):
if w-weight[i-1]<0:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w-weight[i-1]]+val[i-1], dp[i-1][w])
print(dp[N][V])此時看著i-1比較別扭，則想一想能不能寫出：
#取到i的weight[i],則剩下dp[i-1][w-weight[i]]
dp[i][w] = max(dp[i-1][w-weight[i]]+val[i], dp[i-1][w])很因為保留0的原因，所以會顯得二維數(shù)組的行列都大了1，想要對齊，就要在weight[]、value[]數(shù)組存入0，使對齊
改進(jìn)后代碼：
# N件物品，一個容量為V的背包
N,V = map(int,input().split())
weight = []
val = []
weight.append(0)
val.append(0)
for _ in range(N):
wi,vi = map(int,input().split())
weight.append(wi)
val.append(vi)
dp = [[0]*(V+1) for _ in range(N+1)] # (N+1)*(V+1)
for i in range(1,N+1):
for w in range(1,V+1):
if w-weight[i-1]<0:
dp[i][w] = dp[i-1][w]
else:
dp[i][w] = max(dp[i-1][w-weight[i]]+val[i], dp[i-1][w])
print(dp[N][V])改進(jìn)靈感來自聽懂不翻車系列之–背包問題
一維數(shù)組滾動優(yōu)化要從后往前覆蓋才可以
暫時不學(xué)，現(xiàn)目標(biāo)不需要節(jié)約空間
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
