动态规划经典例题，C++解决01背包，车间资源分配，硬币兑换问题

在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。

注意：在本题中，所有的体积值均为整数。

//01背包 #include<iostream> using namespace std; int main() { int c,n; //容量，物品个数 int i,j; cin>>c>>n; int *w=new int[n+1]; int *v=new int[n+1]; for(i=0;i<n;i++) cin>>w[i]>>v[i]; int **dp=new int*[n+1]; for( i=0;i<=n;i++) dp[i]=new int[n+1]; for(i=0;i<=n;i++) { dp[0][i]=0; dp[i][0]=0; } for(i=1;i<=n; i++) { for(j=0;j<=c;j++) { if(j < w[i]) dp[i][j]= dp[i-1][j]; else dp[i][j]= max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]); } } cout<<dp[i][j]; for( i=0;i<n;i++) delete [] dp[i]; delete[] dp; return 0; }

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

再看一个例子：

资源分配问题

//资源分配问题 /*某厂根据计划安排，拟将n台相同的设备分配给m个车间， 各车间获得这种设备后，可以为国家提供盈利Ci j (i台设备提供给j号车间将得到的利润，1≤i≤n，1≤j≤m) 。 问如何分配，才使国家得到最大的盈利？*/ #include<iostream> #include<stdlib.h> #include<time.h> using namespace std; const int n=30; //测试用例：30台设备 const int m=10; //10个车间 int max(int a,int b) { return a>b?a:b; } int main() { int p[n+1][m+1]={0}; //p[i][j]表示i台设备分配给前j号车间最大利润 int c[n+1][m+1]={0}; //c[i][j]表示i台给第j号车间所得利润。 int i=0,j=0; clock_t starttime,endtime; srand((unsigned)time(NULL)); //随机数种子初始化 starttime=clock(); //开始时间 for(i=1;i<=n;++i) for(j=1;j<=m;++j) c[i][j]=(rand()%9)+1; //范围：(0,1000) for(i=1;i<=n;++i) { for(j=1;j<=m;++j) { p[i][j]=p[i][j-1]; for(int k=0;k<=i;++k) p[i][j]=max(p[i][j],(p[i-k][j-1]+c[k][j])); } } endtime=clock(); cout<<"利润表(第i行j列表示i台给设备第j号车间所得利润)："<<endl; for(i=1;i<=n;++i) { for(j=1;j<=m;++j) cout<<c[i][j]<<" "; cout<<endl; } cout<<"最大利润表："<<endl; for(i=0;i<=n;++i) { for(j=0;j<=m;++j) { cout<<p[i][j]<<" "; } cout<<endl; } cout<<"耗费时间："<<(double)(endtime-starttime)*1000/CLOCKS_PER_SEC<<"ms"; return 0; }

这里取n=4,m=2的运行结果： 看另一个动态规划例子：

硬币兑换

怎么样才能用最少的硬币凑出给出的金额？

//动态规划的零钱兑换，不是贪心 //求零钱的最少数量组合，每种硬币不限个数 #include<iostream> #include<vector> using namespace std; int coinchange(vector<int> coins,int num) { int result[num+1]={0}; //num[i]表示i块钱需要的最少零钱数 for(int i=1;i<=num;++i) { int min=INT_MAX; for(int j=0;j<coins.size();++j) { int left=i-coins[j]; //假设coins[j]可以花掉 if(left>=0 && result[left]!=-1) //-1代表不能凑出这个金额 { min=(result[left]<min)?result[left]:min; } result[i]=(min==INT_MAX)?-1:min+1; //这个组合可以，数目+1 } } return result[num]; } int main() { vector<int> test; test.push_back(1); test.push_back(3); test.push_back(5); //可以用的硬币种类 cout<<coinchange(test,11); }