• 大佬整理的理解鏈接：(建議先看一遍自行理解DP思想再去看代碼）

動態規劃之01背包問題 - kkbill - 博客園01背包問題 問題描述： 給定 n 件物品，物品的重量為 w[i]，物品的價值為 c[i]。現挑選物品放入背包中，假定背包能承受的最大重量為 V，問應該如何選擇裝入背包中的物品，使得裝入背包中物品的總https://www.cnblogs.com/kkbill/p/12081172.html

• 思路?

DP算法核心思想： 過利用已有的子問題信息高效求出當前問題的最優解。

?? ?f[i][j]表示只看前i個物品，總體積是j的情況下，總價值最大是多少。
?? ?result=max(f[n][0~v])?
?? ?
?? ?f[i][j]:
? ? （1）、不選第i個物品，f[i][j]=f[i-1][j];
?? ?理解：不選第i個物品有兩種情況：
? ? ? ? a.?體積不夠
? ? ? ? b. 不是最優解，即f[i-1][j]為優解
? ?（ 2）、選擇第i個物品，f[i][j]=f[i-1][j-v[i]]+w[i]
?? ?理解：這里用到了以前已經解決了的子問題，即f[i-1][j-v[i]]的最優解?
?? ?
?? ?eg：新加的物品體積為2，價值為4，假設體積夠裝,則f[i][j]=max(f[i-1][j-2]+4,f[i-1][j])?
?? ??? ?如果體積不夠裝，則f[i][j]=f[i-1][j]?
?? ??? ?
?? ?f[j]:
?? ?狀態轉移方程為：f[j] = max(f[j], f[j - v[i]] + w[i]） 。(我在題目中用f1[N]來表示優化后的一維數組)

? ? ? ? 需要注意的是，一維版本需要逆序求最大值，即從j=m開始，防止數據被覆蓋污染

代碼：

#include<iostream> #include<algorithm> using namespace std;const int N=1010;int n,m; int f[N][N]; //i個物品在總體積小于等于j的情況下可以獲得的最大價值 int v[N],w[N]; //分別表示第i個物品的體積和價值 int f1[N]; //優化的一維版數組 //二維版 int main() {cin>>n>>m; //背包里有n個東西，能裝的物品的體積總和不超過mfor(int i=1;i<=n;i++) cin>>v[i]>>w[i]; //全局變量初始值默認為0，此步驟可省略for(int i=1;i<=n;i++)for(int j=0;j<=m;j++){//不選擇第i個物品f[i][j]=f[i-1][j];//選擇第i個物品if(j>=v[i]) //當前背包的體積可以裝下第i個物品{f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);} } //f[n][m]即為最大值 cout<<f[n][m];} //優化--一維版 int main() {cin>>n>>m;for(int i=1;i<=n;i++) cin>>v[i]>>w[i];for(int i=1;i<=n;i++)for(int j=m;j>=v[i];j--)f1[j]=max(f1[j],f1[j-v[i]]+w[i]);cout<<f1[m];return 0; }

總結

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

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