普通背包问题可以用贪心来解决, 而 0-1 背包问题只能靠动态规划来做, 而且在我们平时的做题中经常会遇到 0-1 背包问题的变形, 所以有必要牢牢掌握 0-1 背包问题的思想和解题思路.
根据下面的图更可以找到应该选那些背包
下面是我根据此思路模拟的代码
- #include<bits/stdc++.h>
- using namespace std;
- int array3[100];// 价值
- int array1[100];// 物品重量
- int capacity;// 容量
- int n;// 物品个数
- int array4[100]={0};// 记录装那些物品
- int array2[100+1][100+1];// 最大价值数组
- int V(int n,int array1[],int array3[]){
- for(int i=0;i<=n;i++){
- array2[i][0]=0;
- }
- for(int j=0;j<=capacity;j++){
- array2[0][j]=0;
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j<=capacity;j++){
- if(j<array1[i]){
- array2[i][j]=array2[i-1][j];
- }
- else{
- array2[i][j]=max(array2[i-1][j],array2[i-1][j-array1[i]]+array3[i]);
- }
- }
- }
- int m=capacity;
- for(int i=n;i>0;i--){
- if(array2[i][m]>array2[i-1][m]){// 记录路径 1 为装入该物品
- array4[i]=1;
- m=m-array1[i];
- }
- }
- return array2[n][capacity];
- }
- int main()
- {
- cout <<"请输入不同物品的总个数 (每个物品都不相同, 即该类物品只有一个)";
- cin>> n;
- cout <<"请依次输入物品的重量" << endl;
- memset(array1,0,sizeof(array1));
- for(int i=1;i<=n;i++){
- cin>> array1[i] ;
- }
- cout <<"请依次输入物品的价值" << endl;
- memset(array3,0,sizeof(array3));
- for(int i=1;i<=n;i++){
- cin>> array3[i] ;
- }
- cout <<"请输入背包的总容量";
- cin>> capacity;
- memset(array2,0,sizeof(array2));
- cout << "可获的最大价值" << V(n,array1,array3) << endl;
- cout << "需要装入的物品是:";
- for(int i=1;i<=n;i++){
- if(array4[i]==1){
- cout <<"物品"<< i << " ";
- }
- }
- return 0;
- }
运行结果如下
总结:(1) 很多 0-1 背包问题完全可以套此模板快速解决问题.(2) 时间复杂度为 o^n2.
来源: http://www.bubuko.com/infodetail-2866565.html