#include<iostream> #include<iomanip> using namespace std; //前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值//0-1背包動(dòng)態(tài)規(guī)劃算法 構(gòu)造二維表 int knapsack_problem( int n,int *weight,int *value,int capacity,int **m,int *flag) {for(int i=0;i<=capacity;i++)//賦值第一行 為0 {m[0][i]=0;// 初始化：背包容量為0時(shí)，前i個(gè)物品無法裝入，獲得最大價(jià)值為0}for(int i=0;i<=n;i++)//第一列賦值為0 {m[i][0]=0;//初始化：物品數(shù)量為0時(shí)，背包容量j無論多大，獲得最大價(jià)值為0} for(int i=1;i<=n;i++) //構(gòu)造二維表：行對(duì)應(yīng)前i個(gè)物品；列對(duì)應(yīng)背包容量j{for(int j=1;j<=capacity;j++){if(j<weight[i]) //背包容量不夠第i個(gè)物品的重量大{m[i][j]=m[i-1][j]; //不裝，獲得的最大價(jià)值仍然等于前i-1個(gè)物品裝入情況的}else{ //裝，看看是裝入后獲得的最大價(jià)值大還是前i-1個(gè)物品裝入情況的最大價(jià)值大，比較后選擇最大的m[i][j]=max(m[i-1][j],m[i-1][j-weight[i]]+value[i]);}}} //標(biāo)記那個(gè)物品最終放到了背包里了嗎 int temp_capacity=capacity;//于背包的最大容量C for(int i=n;i>0;i--)//從后往前遍歷，如果裝了第i個(gè)物品則標(biāo)志位x[i]=1{if(m[i][temp_capacity]>m[i-1][temp_capacity])//判斷第i個(gè)物品有沒有裝進(jìn)去{flag[i]=1; //第i個(gè)物品裝了進(jìn)去temp_capacity=temp_capacity-weight[i];//裝了進(jìn)去就將該物品的重量減去，j為剩余容量}else{flag[i]=0;//第i個(gè)物品沒裝進(jìn)去}}cout << "選中的物品是:";for(int i=1;i<=n;i++){cout<<flag[i]<<" ";}cout<<endl;return m[n][capacity];} int main() {int n,capacity;cout<<"請(qǐng)輸入背包的最大容量：";cin>>capacity;cout<<"請(qǐng)輸入物品的總數(shù)：";cin>>n;int weight[n+1],value[n+1];cout<<"請(qǐng)輸入物品的重量：";for(int i=1;i<=n;i++){cin>>weight[i];}cout<<"請(qǐng)輸入物品的價(jià)值：";for(int i=1;i<=n;i++){cin>>value[i];}int **m=new int *[n+1];//開辟行 for(int i=0;i<=n;i++){m[i]=new int [capacity+1];//開辟列 }int flag[n+1];cout<< "獲得的最大價(jià)值為:"<<knapsack_problem(n,weight,value,capacity,m,flag)<<endl;for(int i=1;i<=n;i++){for(int j=1;j<=capacity;j++){cout<<setw(4)<<m[i][j]<<" ";}cout<<endl;}}

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析——动态规划——01背包问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。