一:前言

這是動態規劃的經典題型，那么我們也是 按照動態規劃五步走的策略分析的

• 確定dp數組的含義以及下標的含義
• 確定dp數組的遞推公式
• 確定dp數組的初始化
• 確定dp數組的遍歷順序
• 舉例驗證（如果不是做題可省略）

二:二維數組

1:示例

2:dp數組的含義

**dp[i][j]**表示的是物品[0,i]放入背包容量為j的時候最大價值

3:確定dp數組的遞推公式

dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])

4:初始化

5：遍歷順序

for(int i = 1; i < weight.size(); i++) {//物品數量 從1開始是因為我們的 我們 for(int j = 0; j <= baseweight; j++) { //第0件物品已經初始化號了if(j < weight[i]) dp[i][j] = dp[i-1][j];else dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])} }

三:一維數組版

1:如何從二維數組變化到一維數組

因為我們是可以壓縮二位數組的,二維數組中的dp[i-1][j] 我們可以 直接拷貝 下來為dp[i][j],
(這個意思就是我們在計算當前方格的時候 直接拿上一個放方格值拿過來，這其實就是不放物品i, 對此我們可以選擇的是放入物品i后的價值+空間的價值與其進行比較)

那二維數組的遞推公式: dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i] );

那么基于此的話 我們可以將其轉化為一維數組

即: dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
(這里的j代表的背包容量 ；
max中的兩部分:dp[j]:不放物品i; dp[j - weight[i]] + value[i]:放入物品i);

2:dp數組的含義

dp[j] 代表的是背包容量為j的時候的最大價值

3:dp數組的遞推公式

即: dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
(這里的j代表的背包容量；
max中的兩部分:dp[j]:不放物品i; dp[j - weight[i]] + value[i]:放入物品i);

4:dp數組的初始化

將其初始化為0 因為我們需要將其中的部分為max部分

5:dp數組的遍歷順序

（1）：正文

這里需要辨析正序遍歷和逆序遍歷

• 正序遍歷（會出現重復計算的值）
  
• 逆序遍歷
  
• 說白了也就正序遍歷的時候 會用到前面已經計算出來的結果 那么就會出現 重復
  那么逆序的時候,我們也是用到前面的dp,但是其還沒有計算出結果初始化為0

（2）：引發的問題（那為啥二維dp數組的背包重量沒有逆序呢?）

一維數組:dp[j-weight[i]] + value[i]
二維數組:dp[i-1][j-weight[i]] +value[i]

• 其實本質上就是比較放入物品i后, 剩余空間的背包容量是否會出現重復放入商品的的狀況
  那么二位數組的話我們是需要先計算出上層的的表格數據（也就是前幾件物品放入背包后的狀況,),因為我們需要計算剩余空間的最大價值。
• 那么我們的一維數組也是需要計算剩余空間的最大價值呀？這樣逆序的話怎么計算？
  對于此的話我們要先明白這是同一件物品 在不同的j(背包容量下的價值)，如果我們正序
  的話，那就相當于將同一間物品放入了不同j下的背包兩次 這是 不允許的，那么逆序就會解決這一切；只要保證了我們同一件物品在不同的j下的正確結果，那么我們才能計算出正確的dp[j]供 dp[j-weight] (求剩余空間的最大價值用)

（3）：上碼

vector<int>dp（n+1）;//總共有n件物品for(int i = 0; i < weight.size(); i++) {//遍歷物品for(int j = baseWeight; j >= weight[i]; j--) {//這里我們只遍歷到weight[i]//是因為如果背包的容量小于weight[i]//的話那么我們是裝不下的 dp[j] = max(dp[j],dp[j-weight[i]] + value[i])}}

總結

以上是生活随笔為你收集整理的背包(二维数组版和一维数组版)的全部內容，希望文章能夠幫你解決所遇到的問題。

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