算法思想:
(1)、动态规划算法:解决背包物品价值最大化问题的最优解,是建立在每一个子问题的最优解的前提下完成的。设Value[i,j]表示的是i个物品放进背包容量为j的背包的价值,令i从0增至n(物品总数量),j从0增至c(背包总容量)。Value[n,c]就是我们要的背包价值最大化的解。为了得到这个解必须要把之前的都解决,每一个问题的最优解的算法又根据以下确定:
当物品重量w小于背包体积j时,此物品不放进背包,价值与上一次价值相同;当物品重量w不小于背包体积j时,此物品是否放进背包,取决于Value[i-1,j]和Value[i-1,j-w]+v的大小。写成表达式则为以下内容:
Value[i-1,j] weight[i]<j
Value[i,j]
Max(Value[i-1,j],Value[i-1,j-w[i]]+v[i]) weight[i]>=j
而这个表达式的约束条件就是当物品数量为0(i=0)时和背包容量为0(j=0)时,最大价值为0。
而要得出背包中放了什么物品也可以根据Value[i,j]是否和Vlaue[i-1,j]相同,如果相同则表示此物品没有放进背包,上一个物品就是第j列;如果不同则放进,而继续寻找上一个的物品的时候,因为本次的坐标来源于j-w[i],所以求出上一个物品的坐标就是用本次坐标+w[i]。
(2)、空间优化算法:动态规划法的空间复杂度为O(nw),现将空间复杂度优化到O(w)。我使用的方法为建立一个新的一维数组V[w+1],此数组与上述动态规划的Value数组不同的是只用于记录上一行的价值,如当我需要求第i行的价值的时候,v数组中存放的是第i-1行的价值。然后从后往前(背包容量从c到0)计算价值、覆盖数组,因为每一次计算背包容量j大小的价值可能会用到j-w的价值,如果从前往后计算的话则数组已被更新,所以要从后往前计算。计算价值的方法也是和上面大致相同:如果物品体积w小于背包容量j,则判断V [j]和V[j-w]+v的大小;如果大于背包容量,则放不进去,V[j]价值不变。
写成表达式如下:
V[j] weight[i]<j
V[j]
Max(V[j],V[j-w[i]]+value[i]) weight[i]>=j
由于使用一维数组的方法,内容还一直被覆盖,所以无法得出背包中具体有哪些物品。
(3)、穷举法:用于验证动态规划方法是否正确。以n=4为例,创建一个v[4]的数组,用0和1表示第i个物品是否放进背包,如0001表示只有第四个物品放进背包。然后数组从0000~1111,计算每次摆放的重量以及价值。如果重量小于背包重量,且价值大于当前最大价值,则记录当前的最大价值以及数组。原理是这样在实施的时候为了记录背包的解,将0000和1111看成0和15的二进制形式,所以让i从0到15进行增长,每次将i转换成二进制格式放进数组中,这样做就可以记录最大价值时的i,转换成二进制则可获得具体物品。
伪代码如下:
For i 0~2n-1
Coverbin( i ) //将i转化成二进制
For j 0~n
If bin[j]==1 //如果第j个物品被放进去,就加上其价值和重量
Sumweigh+=weigh[j]
Sumvalue+=value[j]
If Sumweigh <=c &&Sumvalue>Maxvalue //如果总重量小于背包体积且价值最大
Maxvalue=Sumvalue
Flag=i
//若要获得背包内的物品直接将flag转成二进制即可
代码如下:
#include <iostream>#include <cmath>#include <ctime>using namespace std;int maxvalue(int a,int b);//返回价值大的void bag(int x[],int i,int j);//计算包内物品int priority(int n,int w);//空间优化算法void violent(int n,int w);//蛮力法void conversion(int x,int b[]);//将int转化成二进制int a[50000][50000];//二维数组int *heavy=new int [100000];//物品重量int *v=new int [100000];//物品价值int max=0;int main(){int n,w;cout<<"请输入物品数量n和背包大小w: ";cin>>n>>w;int i,j;for(i=1;i<=n;i++){heavy[i]=(rand()%w)+1;v[i]=(rand()%w)+1; //随机生成物品重量和价值// cout<<heavy[i]<<" "<<v[i]<<endl;}for(i=0;i<=w;i++)a[0][i]=0;for(i=0;i<=n;i++)a[i][0]=0;//将二维数组i=0和j=0的情况都填0clock_t start, end;start = clock();//开始计时for(i=1;i<=n;i++){for(j=1;j<=w;j++){if(heavy[i]>j) //如果重量比容量j大,就不放了a[i][j]=a[i-1][j];else //能放进去{int k=j-heavy[i]; a[i][j]=maxvalue(a[i-1][j],(a[i-1][k]+v[i]));}}}end = clock();//结束计时/*for(i=0;i<=n;i++){for(j=0;j<=w;j++)cout<<a[i][j]<<" ";//输出二维数组表cout<<endl;}*/int *x=new int [n+1];for(i=1;i<=n;i++)x[i]=0;bag(x,n,w);//求包内的物品编号cout<<"最大价值为:"<<a[n][w]<<endl;cout<<"能放进背包的物品编号是: ";for(i=1;i<=n;i++)if(x[i]==1)cout<<i<<" ";cout<<endl;cout<<"运行的时间是(s): ";cout<<(double)(end - start) / (CLOCKS_PER_SEC)<<"s "<<endl;cout<<endl;cout<<"使用一维数组得出最大的价值为:";for(i=1;i<=n;i++)x[i]=0;cout<<priority(n,w)<<endl;cout<<endl;violent(n,w);cout<<"使用蛮力法得出的最大价值为:";cout<<max<<endl;return 0;}int maxvalue(int a,int b){if(a<b)return b;elsereturn a;}void bag(int x[],int i,int j){if(i<0)return ;if(a[i][j]==a[i-1][j]) //如果和上一列的数字相同,则表示该物品没放bag(x,i-1,j);else //和上一列的不同{x[i]=1;//该物品放进去了bag(x,i-1,j-heavy[i]);//继续找上一个物品是否放进去了}}int priority(int n,int w){int i,j;int *bag=new int [w+1];//数组用于保存上一行的数据for(i=0;i<w+1;i++)bag[i]=0;//第一行先置0for(i=1;i<=n;i++)for(j=w;j>=heavy[i];j--)//从后往前判断,当背包容量大于物品重量{if(bag[j]<bag[j-heavy[i]]+v[i])//两个价值谁大填哪个bag[j]=bag[j-heavy[i]]+v[i];}int end=bag[w];//最大价值就是数组最后一个return end;}void violent(int n,int w){int i,j,sumw,sumv,flag=0;int bin[10];for(i=0;i<pow(2,n);i++)//n等于4的话,二进制从0000~1111即0~15{for(j=1;j<=n;j++)bin[j]=0;//初始化数组conversion(i,bin);//转换成二级制sumw=0;sumv=0;for(j=1;j<=n;j++)if(bin[j]==1)//如果放了这个物品{sumw=sumw+heavy[j];sumv=sumv+v[j];//重量相加,价值相加}if(sumw<=w)if(sumv>max) //当总重量小于背包重量且价值大于当前最大价值时{max=sumv; //记录最大价值flag=i; //记录当前i}}for(j=1;j<=n;j++)bin[j]=0;conversion(flag,bin); //将最大价值的i转换成二进制,得出背包物品编号cout<<"能放进背包的物品编号是: ";for(j=1;j<=n;j++)if(bin[j]==1)cout<<j<<" ";cout<<endl;}void conversion(int x,int b[]) //转化成二进制{int i;for(i=1;;i++){b[i]=x%2;x=x/2;if(x==0)break;}}