爱华网背包，并使包内物品价值最大 2. 问题分析 在0/1背包问题中，物体或者被装入背包，或者不被装入背包，只有两种选择。 循环变量i，j意义：前i个物品能够装入载重量为j的背包中 (n+1)*(m+1)数组value意义：value[i][j]表示前i个物品能装入载重量为j的背包中物
品的最大价值 若w[i]>j，第i个物品不装入背包 否则，若w[i]<=j且第i个物品装入背包后的价值>value[i-1][j]，则记录当前最大价值
（替换为第i个物品装入背包后的价值） 计算最大价值的动态规划算法如下： //计算 for(i=1;i { for(j=1;j { //w[i]>j,第i个物品不装入背包 value[i][j]=value[i-1][j]; //w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值 inttemp=value[i-1][j-w[i]]+v[i]; if(w[i]<=j&&temp>value[i][j]) value[i][j]=temp; } } 即该段程序完成以下n个阶段： 1：只装入1个物品，确定在各种不同载重量的背包下，能够得到的最大价值 2：装入2个物品，确定在各种不同载重量的背包下，能够得到的最大价值 。。。 n：以此类推，装入n个物品，确定在各种不同载重量的背包下，能够得到的最大价值 3. 问题求解 确定装入背包的具体物品，从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]; } } 4. 代码如下 输入数据及输出数据均在文件中。 输入数据格式： n m w1 w2 ... wn v1 v2 ... vn 输出数据格式： maxValue i count //i表示物品编号，count表示该物品被选中次数 ...#include#include#include#define FILENAMELENGTH100class 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 openfile!"); 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;}int CBeibao::GetMaxValue(int n,intm,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 value[i]=newint[col]; //初始化第0行 for(j=0;j value[0][j]=0; //初始化第0列 for(i=0;i value[i][0]=0; //计算 for(i=1;i { for(j=1;j { //w[i]>j,第i个物品不装入背包 value[i][j]=value[i-1][j]; //w[i]<=j,且第i个物品装入背包后的价值>value[i-1][j],则记录当前最大价值 inttemp=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 { delete[col]value[i]; value[i]=NULL; } delete[] value; value=NULL; return nMaxVlaue;}intCBeibao::GetMaxValue(){ intnValue=GetMaxValue(m_nNumber,m_nMaxWeight,m_pWeight,m_pValue,m_pCount); m_nMaxValue=nValue; return nValue;}//显示结果void CBeibao::Display(intnMaxValue){ 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(intnMaxValue,const char *filename){ FILE *fp=fopen(filename,"w"); if(fp==NULL) { printf("can not writefile!"); 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 afilename:"); scanf("%s",sfilename); //获取满足最大载重量的最大价值 CBeibao beibao(sfilename); intnMaxValue=beibao.GetMaxValue(); if(nMaxValue) { beibao.Display(nMaxValue); intnlen=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); }} 5. 运行结果如下 文件中的内容如下：1. input.txt 4 10 2 3 4 7 1 3 5 9 input_result.txt 12 21 41 2. input1.txt 5 10 2 2 6 5 4 6 3 5 4 6 input1_result.txt 15 11 21 51 3. input2.txt 5 15 2 6 4 7 9 1 6 5 9 4 input2_result.txt 16 11 21 41 4. input3.txt 10 105 12 16 24 7 29 32 5 43 311 11 16 15 9 24 25 3 32 417 input3_result.txt 112 11 21 41 61 71 91 10 1
