學習交流加

• 個人qq：
  1126137994
• 個人微信：
  liu1126137994
• 學習交流資源分享qq群：
  962535112

一個背包有一定的承重cap，有N件物品，每件都有自己的價值，記錄在數組v中，也都有自己的重量，記錄在數組w中，每件物品只能選擇要裝入背包還是不裝入背包，要求在不超過背包承重的前提下，選出物品的總價值最大。

給定物品的重量w價值v及物品數n和承重cap。請返回最大總價值。

測試樣例：
[1,2,3],[1,2,3],3,6
返回：6

這個背包問題，還是很不好理解的其實！

解題思路：
假設物品編號為1~n，一件一件考慮是否裝入背包內。有兩個變量w（代表各個物品的重量數組）和v（代表各個物品的價值數組）。同樣還是開辟一個新的空間，大小為dp[n][cap],那么，dp[i][j]代表前i件物品，且背包承重為j時的物品最大價值！！那么dp[n][cap]就是我們的最終所求，即矩陣的最右下角！！！

求解步驟：
1、求第一行：
dp[0][j]代表前0件物品的價值，都為0，所以dp[0][j]=0
2、求第一列：
dp[j][0]代表前j件物品，但是背包的承重為0，所以總價值也是都為0，所以dp[i][0]=0
3、求其他行：
dp[i][j]代表前i件物品，背包的承重為j時，所能獲得的最大價值。可以分為以下兩種情況：
一：拿第i件物品
拿第i件物品的時候，首先要保證（條件判斷）第i件物品的重量w[i-1]（注意這里為什么是i-1，因為數組w是從0號開始，它的0號對應的是矩陣第一列的1號，當矩陣的為i時，對應的w里應該是i-1）不能超過j(超過j就不會拿第i件產品了)。而當我們拿了第i件物品后，前i-1件的物品獲得的最大價值也會重新分布（有可能會減少），此時到底是拿第i件物品后價值大還是不拿第i件物品產品大呢？這個是不確定的，所以需要去判斷選擇.
1）拿的話，價值應該等于 v[i-1]（第i件物品的價值，為什么是i-1原因與w[i-1]一樣）加上前i-1件物品，背包承重j-w[i-1]的價值
2）不拿的話，價值就直接等于dp[i-1][j]
然后選擇上述的較大值就行
此時：

if(j>w[i-1])dp[i][j] = max(dp[i-1][j],v[i-1]+dp[i-1][j-w[i-1]])

二：不拿第i件物品
當我想拿第i件物品時，如果w[i-1]>j,就不能拿，因為一拿就超過背包的承重。所以此時的價值就直接等于前i-1件物品，背包承重i時的價值！
即：

if(j<w[i-1])dp[i][j] = dp[i-1][j];

最終的代碼如下：
運行通過了所有的測試用例！

class Backpack { public:int maxValue(vector<int> w, vector<int> v, int n, int cap) {// write code hereint dp[n+1][cap+1];//初始化一列for(int i=0;i<n+1;i++)dp[i][0]=0;//初始化第一行for(int j=0;j<cap+1;j++)dp[0][j]=0;//求其他行的值 for(int i=1;i<n+1;i++){for(int j=1;j<cap+1;j++){//拿第i件物品,拿了后的總價值不一定比不拿前的總價值高（因為拿了第i件物品后，前面的i-1件物品的分配匯會改變）if((j-w[i-1])>=0)dp[i][j]=max(v[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);//不拿第i件物品elsedp[i][j]=dp[i-1][j]; }}return dp[n][cap];} }; 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【常见笔试面试算法题12续集五】动态规划算法案例分析5 01背包练习题的全部內容，希望文章能夠幫你解決所遇到的問題。

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