很簡單但是需要特別注意的，一定不要錯。

背包：
有n 種不同的物品，每個物品有兩個屬性，v體積，c價值，現(xiàn)在給一個體積為 m 的背包，問最多可帶走多少價值的物品。
??????狀態(tài)轉(zhuǎn)移方程??dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+c[i])
dp[i-1][j]表示不放第i件物品的最大價值，dp[i-1][j-v[i]]+c[i]表示放第i件物品的最大價值；[i-1][j-v[i]]這個表示將????前i-1件物品放入空間為??j-v[i] 的背包中的最大價值。為啥要j-v[i]?？因為要放第i件物品，所以所剩空間就剩了??????j-v[i].??所以[i-1][j-v[i]]+c[i]就表示放第i件物品的最大價值。

?

（1）背包不一定裝滿。
dp[j]記錄的是前i件物品放入空間為j的背包中的最大價值！！！
要在一開始，讓dp[1001]中的每個值為 0;

（2）背包剛好裝滿 ???

背包剛好裝滿需要注意：

要把f[j]??(表示剛好裝滿的最大價值) 這樣初始化！

f[0]=0; f[1~n]=負(fù)無窮-inf

（注意：codeblocks中沒有直接表示無窮的符號，inf是自己定義的）

因為這樣就能是那些能夠恰好裝滿背包的物品的值為正數(shù)！而那些不能恰好裝滿背包的物品 的值就為負(fù)數(shù)。

這樣就容易區(qū)分了。

這樣dp（n）（背包最多承重） == inf話，說明裝不滿，裝滿的話 如果要求裝滿最多的價值，直接輸出dp【n】

總結(jié)

以上是生活随笔為你收集整理的动态规划-背包是否装满的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。