回溯法-0-1背包问题.doc

《回溯法-0-1背包问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、问题描述一、0-1背包问题给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择才能使得物品的总价格最高？2、算法设计思想回溯法3、算法过程描述1.解空间的定义物品有装入和不装入两种状态，设装入为1，不装入为0，例如n=3时，解空间为{（0,0,0），（0,0,1）……（1,1,1）}2.解空间结构的组织使用一棵子集树来表示解空间每一条边的权值代表装或不装（1或0）采用深度优先搜索遍历整个树3.约束条件1）重量不超过背包的容量2）已装入物品的价值Cp+剩余空间装入物品的最大价值r<=最优解bes

2、tP注*：最大价值r的求法：假设物品能够分割，运用贪心算法的思想，求出背包理论最大价值r4、算法实现及运行结果#includeintn,c,bestp;//物品的个数，背包的容量，最大价值intp[10000],w[10000],x[10000],bestx[10000];//物品的价值，物品的重量，x[i]暂存物品的选中情况,物品的选中情况voidBacktrack(inti,intcp,intcw){//cw当前包内物品重量，cp当前包内物品价值intj;if(i>n)//回溯结束{if(cp

3、>bestp){bestp=cp;for(i=0;i<=n;i++)bestx[i]=x[i];}}elsefor(j=0;j<=1;j++){x[i]=j;if(cw+x[i]*w[i]<=c){cw+=w[i]*x[i];cp+=p[i]*x[i];Backtrack(i+1,cp,cw);cw-=w[i]*x[i];cp-=p[i]*x[i];}}}intmain(){inti;bestp=0;printf("请输入背包最大容量:");scanf("%d",&c);printf("请输入物品个数:")

4、;scanf("%d",&n);printf("请依次输入物品的重量:");for(i=1;i<=n;i++)scanf("%d",&w[i]);printf("请依次输入物品的价值:");for(i=1;i<=n;i++)scanf("%d",&p[i]);Backtrack(1,0,0);printf("最大价值为:");printf("%d",bestp);printf("被选中的物品依次是(0表示未选中，1表示选中)");for(i=1;i<=n;i++)printf("%d",best

5、x[i]);printf("");return0;}1、算法复杂度分析及算法改进时间复杂度为O(2^n)*O(n)(求上界)=O(n2^n)