01背包:

#include<algorithm> #include<cstdio> using namespace std; int main() ///01背包,每種物品的個數為1個 {int n,m;while(scanf("%d%d",&n,&m)!=EOF) ///在n個物品中選擇若干物品,使得體積在m以內時,物品總價值最大{int v[1025]={0},w[1025]={0},dp[1025]={0};for(int i=0;i<n;i++)scanf("%d%d",&v[i],&w[i]); ///v[i]為第i個物品的體積,w[i]為第i個物品的價值for(int i=0;i<n;i++) ///i<物品個數for(int j=m;j>=v[i];j--) ///j=擁有的容量,如果j<v[i],則沒必要往下計算,跳出循環.(逆序遍歷)dp[j]=max(dp[j],dp[j-v[i]]+w[i]);///比較dp[j]時候的價值和dp[j-v[i]]+w[i]的價值,看替換上第i個物品是否會使價值提升printf("%d\n",dp[m]);}return 0; }

完全背包:

#include<cstdio> #include<algorithm> using namespace std; int main() ///完全背包,每種物品的個數為無限個 {int n,m;while(scanf("%d%d",&n,&m)!=EOF) ///在n個物品中選擇若干物品,使得體積在m以內時,物品總價值最大{int v[1025]={0},w[1025]={0},dp[1025]={0};for(int i=0;i<n;i++)scanf("%d%d",&v[i],&w[i]); ///v[i]為第i個物品的體積,w[i]為第i個物品的價值for(int i=0;i<n;i++) ///i<物品個數for(int j=v[i];j<=m;j++) ///判斷該裝幾個第i種物品.(正序遍歷)dp[j]=max(dp[j],dp[j-v[i]]+w[i]);///比較dp[j]時候的價值和dp[j-v[i]]+w[i]的價值,看替換上第i個物品是否會使價值提升printf("%d\n",dp[m]);}return 0; }

?

轉載于:https://www.cnblogs.com/wangtao971115/p/10358324.html

總結

以上是生活随笔為你收集整理的背包模板的全部內容，希望文章能夠幫你解決所遇到的問題。

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