《算法分析回溯法实现0-1背包(c++).doc》由会员分享，可在线阅读，更多相关《算法分析回溯法实现0-1背包(c++).doc（4页珍藏版）》请在金锄头文库上搜索。
1、本程序实现0-1背包问题算法 (回溯法) /*本程序实现0-1背包问题算法 (回溯法)*/#include using namespace std;#define MAXSIZE 100#define TRUE 1#define FALSE 0#define ERROR -1typedef float value;typedef float weight;typedef int KeyType; / 定义关键字类型为整数类型typedef struct /元素定义weight w;/重量value v;/价值value q;/单位重量价值int index;/序号bool job;/表示是否被
2、用Bag;typedef struct /定义背包集Bag rMAXSIZE+1;/r0闲置或用作 “ 哨兵单元”int length; /背包个数Bags;int n;/包个数int i;/辅助整型变量 weight c;/背包的容量weight cw;/当前重量value bestp=0;/当前最优价值value cp;/当前价值Bags L;/定义背包集int Partition(Bags &L,int low,int high) /快速排序/ 交换顺序表L中子表rlow.high的记录,枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大于它.int shuzhou; /定义
3、枢轴L.r0=L.rlow; /用第一个记录作为枢轴记录shuzhou=L.rlow.q;while(lowhigh) while(low=shuzhou) -high; L.rlow=L.rhigh; while(lowhigh & L.rlow.q=shuzhou) +low; L.rhigh=L.rlow; L.rlow=L.r0;return low; /Partitionvoid QuickSort(Bags &L,int low,int high) /快速排序/对顺序表Llow .high作快速排序int shuzhou;if(lowhigh) shuzhou=Partition(
4、L,low,high); / 获得枢轴 QuickSort(L,low,(shuzhou-1); /对枢轴前半部分排序 QuickSort(L,(shuzhou+1),high); /对枢轴后半部分排序 /QuickSortvalue bound(int i)/计算上界weight left=c-cw;/剩余容量value bound=cp;/以物品单位重量价值递减顺序装入物品while(i=n&L.ri.w=left) left-=L.ri.w; bound+=L.ri.v; i+;/装满背包if(in)/到达叶子结点 bestp=cp; return ;/搜索子树if(cw+L.ri.wb
5、estp)/进入右子树 backtrack(i+1);/backtrackvoid knapsack(weight c)/0-1背包问题主算法QuickSort(L,1,L.length);backtrack(1);/回溯搜索/knapsackint main()/输入要选择的背包信息cout请输入背包的容量:c; cout请输入背包个数（注意：最大作业数不能超过 100个!）：n;if(n100) cout你输入的背包个数太大!endl; return FALSE;L.length=n; cout请输入各个背包的信息： endl;for(i=1;i=n;i+) cout请输入第个iL.ri.w; cout请输入第个iL.ri.v; L.ri.q=L.ri.v/L.ri.w;/单位重量价值 L.ri.index=i;/索引号 coutendl;/执行0-1背包问题主算法knapsack(c);/输出结果for(i=1;i=n;i+) if(L.ri.job) cout第个L.ri.index背包被选中endl;cout被选中的背包的总价值为： bestpendl;return TRUE;
