背包问题

背包问题是在1978年由Merkel和Hellman提出的，主要思路是假设某人拥有大量物品，物品的重量都不相同。此人通过秘密地选择一部分物品，并将物品放到背包中来加密消息。背包中物品的重量是公开的，所有可能的物品也是公开的，但背包中装的物品种类是保密的。背包问题的题目要求是：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择才能使物品的总价格最高。

1　使用动态规划法

实例　使用动态规划法解决“背包”问题

问题描述：设定一个载重量为m，有n个物品，其重量为wi，价值为vi，1<=i<=n，要求把物品装入背包，并使包内物品价值最大。

算法分析：在背包问题中，物品要么被装入背包，要么不被装入背包。设置循环变量i，前i个物品能够装入载重量为j的背包中。用value[i][j]数组表示前i个物品能装入载重量为j的背包中物品的最大价值。如果w[i]>j，第i个物品不装入背包；如果w[i]<=j且第i个物品装入背包后的价值>value[i−1][j]，则记录当前最大价值（替换为第i个物品装入背包后的价值）

计算最大价值的动态规划算法如下所示。

 //计算 for(i=1;i<row;i++) ...{ for(j=1;j<col;j++) ...{ //w[i]>j,第i个物品不装入背包 value[i][j]=value[i-1][j]; //w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值 int temp=value[i-1][j-w[i]]+v[i]; if(w[i]<=j && temp>value[i][j]) value[i][j]=temp; } }

上述程序段完成以下n个阶段。

① 只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值。

② 装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值。

….以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值。

确定装入背包的具体物品，从value[n][m]向前开始逆推。如果value[n][m]>value[n-1][m]，则第n个物品被装入背包，且前n−1个物品被装入载重量为m−w[n]的背包中；否则，第n个物品没有装入背包，且前n−1个物品被装入载重量为m的背包中。按照上述方法类推，直到确定第一个物品是否被装入背包为止。逆推代码如下所示。

 //逆推求装入的物品 j=m; for(i=row-1;i>0;i--) ...{ if(value[i][j]>value[i-1][j]) ...{ c[i]=1; j-=w[i]; } }

具体实现：编写实例文件13-2.c，具体实现代码如下所示。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define FILENAMELENGTH 100class cbeibao{public: int m_nNumber; //物品数量 int m_nMaxWeight; //最大载重量 int *m_pWeight; //每个物品的重量 int *m_pValue; //每个物品的价值 int *m_pCount; //每个物品被选中的次数 int m_nMaxValue; //最大价值public: CBeibao(const char *filename); ～CBeibao(); int GetMaxValue(); int GetMaxValue(int n,int m,int *w,int *v,int *c); void Display(int nMaxValue); void Display(int nMaxValue,const char *filename);};//读入数据CBeibao::CBeibao(const char *filename)...{ FILE *fp=fopen(filename,"r");  if(fp==NULL) ...{ printf("can not open file!"); return; //exit(0); } //读入物品数量和最大载重量 fscanf(fp,"%d%d",&m_nNumber,&m_nMaxWeight); m_pWeight=new int[m_nNumber+1]; m_pValue=new int[m_nNumber+1]; m_pWeight[0]=0; //读入每个物品的重量 for(int i=1;i<=m_nNumber;i++) fscanf(fp,"%d",m_pWeight+i); m_pValue[0]=0; //读入每个物品的价值 for(int i=1;i<=m_nNumber;i++) fscanf(fp,"%d",m_pValue+i); //初始化每个物品被选中次数为0 m_pCount=new int[m_nNumber+1]; for(int i=0;i<=m_nNumber;i++) m_pCount[i]=0; fclose(fp);}CBeibao::～CBeibao()...{ delete[] m_pWeight; m_pWeight=NULL; delete[] m_pValue; m_pValue=NULL; delete[] m_pCount; m_pCount=NULL;}/**//************************************************************************ * 动态规划求出满足最大载重量的价格最大值 * 参数说明：n:物品个数 * m:背包载重量 * w:重量数组 * v:价值数组 * c:是否被选中数组 * 返回值：最大价值 ************************************************************************/int CBeibao::GetMaxValue(int n,int m,int *w,int *v,int *c)...{ int row=n+1; int col=m+1; int i,j; //循环变量:前i个物品能够装入载重量为j的背包中 //value[i][j]表示前i个物品能装入载重量为j的背包中物品的最大价值 int **value=new int*[row]; for(i=0;i<row;i++) value[i]=new int[col]; //初始化第0行 for(j=0;j<col;j++) value[0][j]=0; //初始化第0列 for(i=0;i<row;i++) value[i][0]=0; //计算 for(i=1;i<row;i++) ...{ for(j=1;j<col;j++) ...{ //w[i]>j,第i个物品不装入背包 value[i][j]=value[i-1][j]; //w[i]<=j,且第i个物品装入背包后的价值>value[i-1] [j],则记录当前最大价值 int temp=value[i-1][j-w[i]]+v[i]; if(w[i]<=j && temp>value[i][j]) value[i][j]=temp; } } //逆推求装入的物品 j=m; for(i=row-1;i>0;i--) ...{ if(value[i][j]>value[i-1][j]) ...{ c[i]=1; j-=w[i]; } } //记录最大价值 int nMaxVlaue=value[row-1][col-1]; //释放该二维数组 for(i=0;i<row;i++) ...{ delete [col]value[i]; value[i]=NULL; } delete[] value; value=NULL; return nMaxVlaue;}int CBeibao::GetMaxValue()...{ int nValue=GetMaxValue(m_nNumber,m_nMaxWeight,m_pWeight,m_pValue,m_pCount); m_nMaxValue=nValue; return nValue;}//显示结果void CBeibao::Display(int nMaxValue)...{ printf(" %d ",nMaxValue); for(int i=1;i<=m_nNumber;i++) ...{ if(m_pCount[i]) printf(" %d %d ",i,m_pCount[i]); } printf(" ");}void CBeibao::Display(int nMaxValue,const char *filename) { FILE *fp=fopen(filename,"w");  if(fp==NULL) ...{ printf("can not write file!"); return; //exit(0); } fprintf(fp,"%d ",nMaxValue); for(int i=1;i<=m_nNumber;i++) ...{ if(m_pCount[i]) fprintf(fp,"%d %d ",i,m_pCount[i]); } fclose(fp);}//显示菜单void show_menu()...{ printf("--------------------------------------------- "); printf("input command to test the program "); printf(" i or I : input filename to test "); printf(" q or Q : quit "); printf("--------------------------------------------- "); printf("$ input command >");}void main()...{ char sinput[10]; char sfilename[FILENAMELENGTH]; show_menu(); scanf("%s",sinput); while(stricmp(sinput,"q")!=0) { if(stricmp(sinput,"i")==0) ...{ printf(" please input a filename:"); scanf("%s",sfilename); //获取满足最大载重量的最大价值 CBeibao beibao(sfilename); int nMaxValue=beibao.GetMaxValue(); if(nMaxValue) ...{ beibao.Display(nMaxValue); int nlen=strlen(sfilename); strcpy(sfilename+nlen-4,"_result.txt"); beibao.Display(nMaxValue,sfilename); } else printf("error! please check the input data!"); } //输入命令 printf("$ input command >"); scanf("%s",sinput); }}

执行后的效果如图13-2所示。

图12　使用动态规划法解决“背包”问题执行效果

2　使用递归法

实例　使用递归法解决“背包”问题

问题描述：假设有一个背包最多能装8 kg物体，假设要使背包能装下下面的水果，并要求背包里面的水果价值最大，问应该装哪些水果符合要求？

苹果：5 kg，40元。梨：2 kg，12元。桃：1 kg，7元。葡萄：1 kg，8元。香蕉：6 kg，48元。

具体实现：编写实例文件13-3.c，其具体实现流程如下所示。

（1）定义结构goods来保存水果的相关信息，具体实现代码如下所示。

typedef struct goods{ double *value; //价值 double *weight; //重量 char *select; //是否选中到方案 int num; //物品数量 double limitw; //限制重量}GOODS;

（2）分别定义全局变量maxvalue、totalvalue和select1，然后定义函数backpack()通过递归方法完成背包的装入操作。具体实现代码如下所示。

double maxvalue,totalvalue;//方案最大价值,物品总价值char *select1; //临时数组//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值void backpack(GOODS *g, int i, double tw, double tv) { int k; if (tw + g->weight[i] <= g->limitw)//将物品i包含在当前方案,且重量小于等于限制重量 { select1[i] = 1; //选中第i个物品 if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw + g->weight[i], tv); //递归调用,继续添加下一物品 else //如果已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到选择数组中 g->select[k] = select1[k]; maxvalue = tv; //保存当前方案的最大价值 } } select1[i] = 0; //取消物品i的选择状态//如果物品总价值减去物品i的价值还大于maxvalu方案中已有的价值,说明还可以继续向方案中添加物品 if (tv - g->value[i] > maxvalue) { if (i < g->num - 1) //若物品i不是最后一个物品 backpack(g, i + 1, tw, tv - g->value[i]); //递归调用,继续加入下一物品 else //若已到最后一个物品 { for (k = 0; k < g->num; ++k) //将状态标志复制到选择数组中 g->select[k] = select1[k]; //保存当前方案的最大价值(从物品总价值中减去物品i的价值) maxvalue = tv - g->value[i];  } }}

（3）定义主函数main()调用上面定义的函数实现背包求解，具体实现代码如下所示。

int main(){ double sumweight; GOODS g; int i; printf("背包最大重量:"); scanf("%lf",&g.limitw); printf("可选物品数量:");  scanf("%d",&g.num); if(!(g.value = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品价值 { printf("内存分配失败\n"); exit(0);  } if(!(g.weight = (double *)malloc(sizeof(double)*g.num)))//分配内存保存物品的重量 { printf("内存分配失败\n"); exit(0);  } if(!(g.select = (char *)malloc(sizeof(char)*g.num))) //分配内存保存物品的重量（选中方案的重量） { printf("内存分配失败\n"); exit(0);  } if(!(select1 = (char *)malloc(sizeof(char)*g.num))) //分配内存保存物品的重量（某类选择物体） { printf("内存分配失败\n"); exit(0);  } totalvalue=0;  for (i = 0; i < g.num; i++) { printf("输入第%d号物品的重量和价值:",i + 1); scanf("%lf%lf",&g.weight[i],&g.value[i]); totalvalue+=g.value[i];//统计所有物品的价值总和 } printf("\n背包最大能装的重量为:%.2f\n\n",g.limitw); for (i = 0; i < g.num; i++) printf("第%d号物品重:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]); for (i = 0; i < g.num; i++)//初始设各物品都没加入选择集 select1[i]=0; maxvalue=0;//加入方案物品的总价值 backpack(&g,0,0.0,totalvalue); //第0号物品加入方案,总重量为0,所有物品价值为totalvalue  sumweight=0;  printf("\n可将以下物品装入背包,使背包装的物品价值最大:\n"); for (i = 0; i < g.num; ++i) if (g.select[i]) { printf("第%d号物品,重量:%.2f,价值:%.2f\n", i + 1, g.weight[i], g.value[i]); sumweight+=g.weight[i]; }  printf("\n总重量为: %.2f,总价值为:%.2f\n", sumweight, maxvalue ); getch(); return 0;}

执行后的效果如图13-3所示。

图3　使用递归法解决“背包”问题执行效果