給定一組有固定價值和固定重量的物品，以及一個已知最大承重量的背包，求在不超過背包最大承重量的前提下，能放進背包里面的物品的最大總價值。要求物品不能分割開來。
01代表裝或不裝。
問題的難點在于哪里呢？

首先最終目的是總價值最大，而承重量則是一個限制條件。一般而言。對于背包問題的貪心算法是計算性價比后優先放入性價比高的物品，由于貪心類問題中允許把物體分開后放入背包，其實并不難。
而在動態分配問題中呢？
物體不能被分割的情況下，如何能做到價值的最大化變成了難點，不一定性價比最高的最后獲得的總價值最高，因為承重量的限制可能導致你在放入性價比最高的物體后，就無法繼續放入了，反而導致總價值不高。
舉個例子：

限重 5 kg 質量： 1 ，2 ， 4 價值：10，16，30

最大價值為40
如果按性價比排名放入只能拿到26了。

因此怎么去考慮這類問題呢？
就拿第一個物品來說
總的問題可以分解為兩個子問題：
①裝第一個物品 我剩余的空間能裝多大價值的物品
②不裝第一個物品 我剩余的空間能裝多大價值的物品
類推到第i個物品：

if(c[i] > j)dp[i][j] = dp[i - 1][j];//情況② elsedp[i][j] = max(p[i - 1][j], p[i - 1][j - w[i]] + v[i]);//①

我慢慢分析這一行代碼。
p[i][j]代表的是在限重為j的情況下，前n個物品能獲得的最大價值。
max是系統函數max，返回兩個值中的較大值。
是哪兩個值呢？
p[ i-1 ][ j ]和 j - w[i] ] + v[ i ] ，分別對應兩種子問題。
p[ i-1 ][ j ]對應的是上面的②，即在不拿第i個物品，在限重為j的情況下，前i-1個物品能取得的最大價值
j - w[i] ] + v[ i ] 對應①，即拿了第i個物品，在限重為j-w[i]（第i個物品確定拿，剩余空間減小了）的情況下，前i-1個物品能拿到的最大價值加上第i個物品的價值

for(int i = 1; i <= N; i++) //i對應第i個物品，i的循環放外面，V[i][] 對應數據由V[i-1][] 決定{for(int j = 1; j <= M; j++) //j對應當前背包能承受重量為j{if(j >= [i]) {p[i][j] = max(p[i - 1][j], p[i - 1][j - w[i]] + v[i]);}else{p[i][j] = p[i - 1][j];}}}

總結

以上是生活随笔為你收集整理的动态规划——01背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。