实验： 0/1 背包问题、 实验目的与要求：熟悉C/C+语言的集成开发环境;通过本实验加深对贪心算法、二、 实验内容：动态规划和回溯算法的理解。掌握贪心算法、动态规划和回溯算法的概念和基本思想，分析并掌握0-1背包问题的三三种算、法，并分析其分析其优缺点。实验题：1. 0-1背包问题的贪心算法2. 0-1背包问题的动态规划算法1. 理解算法思想和问题要求;2. 编程实现题目要求;3. 上机输入和调试自己所编的程序4. 验证分析实验结果;5. 整理出实验报告。五、 实验程序：贪心算法：#include #include #include #include windows.hstruct goodinfoint p; /物品效益int w; /物品重量int X; /物品该放的数量float rat“/物品效益，重量比int flag; /物品编号;/物品信息结构体void Insertionsort(goodinfo goods,int n)int j,i;for(j=2;jgoodsi.rat) goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益，重量比值做升序排列void bag(goodinfo goods,int M,int n)int cu;int i,j,value=0,weight=0; for(i=1;i=n;i+) goodsi.X=0;cu=M; /背包剩余容量 for(i=1;icu)当该物品重量大与剩余容量跳出 break;goodsiX=1; value+=goodsip; weight+=goodsiw;cu=cu-goodsi w;/确定背包新的剩余容量/ if(i=n)/goodsi.X=cu/goodsi w;/该物品所要放的量for(j=2;j=n;j+)/*按物品编号做降序排列*/goods0=goodsj;i=j-1;while (goods0.flaggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;coutvv要放的物品有：； for(i=1;i=n;i+)if(goodsiX=1)couti coutvvendl;coutvv包内物品的总价值：#define n 5#define m 10void knapbag(int *w,int *vl)int cn+1m+1;从liitem物品中，背包剩余空间为0v=jv=max_wgt的最大价值for (i=0;iv=n;i+)/初始化for (int j=0;jv=m;j+)cij=0;/c(i,j)=maxc(i-1,j), c(i-1,j-wi)+vl(i)for (i=1;iv=n;i+)for (int j=1;jv=m;j+)if (wiv=j)if (vli+ci-1j-wici-1j)cij=vli+ci-1j-wi;/选择第 i 物品elsecij=ci-1j;/不选择第 i 个物品elsecij=ci-1j;/剩 余容量不够/endfor/endforcoutvv最优解：；coutvvcnmvvend l;/返回最大值/算出是由哪几个物品组成int temp_wei=m;int xn+1=0,0,0,0;for (i=n;i0;i-)if (citemp_wei=ci-1temp_wei)/Z最后一个肯定是最大价值的xi=0;elsexi=1;temp_wei-=wi;coutvv应装入的物品有：；for (i=0;iv=n;i+)if (xi)coutvv第vvivv件t;coutvvendl;int main()int i=0int w6=0,2,2,6,5,4;物品质量int vl6=0,6,3,5,4,6; /物品价值knapbag(w,vl);return 0;回溯法：#include viostream.hint min(int a,int b)if(a=b) return b;else return a;int max(int a,int b)if(a=b) return a;else return b;void Knapsack(int v6,int w6,int c,int n,int m66) int jmax=min(wn-1,c);for(int j=0;jvjmax;j+)mnj=0;for(int p=wn;pv=c;p+) mnp=vn;for(int i=n-1;i1;i-)jmax=min(wi-1,c); for(int j=0;j=jmax;j+) mij=mi+1j;for(int t=wi;t=w1)m1c=max(m1c,m2c-w1+v1);void Traceback(int m66,int w6,int c,int n,int x6)for(int i=1;ic1;coutvv0-1 背包问题是： vvendl;coutvv物品的重量分别为：vvendl;for(int p=1;pv6;p+)coutvvw1pvv ;coutendl;coutvv物品的价值分别为：vvendl;for(int q=1;q6;q+)coutvvv1qvv ;coutvvendl;coutvv背包的容量为：vvclvvendl; */ coutvv要选择的物品是:vvendl;Knapsack(v1,w1,c1,n1,t); for(int i=1;iv=n1;i+)coutvvv1ivvendl;Traceback(t,w1,c1,n1,x1);for(int i=1;iv=n1;i+) if(x1i=1) m+=v1i;coutvv第v vivv件物品vvendl; return 0;六、 实验结果：贪心：I C:UsersSa ku raAp pDataRoam i ngM i crosoftW i nd owsSta rt Men liP ro g ra msCode Bl c.回有忌0. 口 : 物口間 的器 舌仃 賣执5512包的当前重量：8Process returned 0 execution time : 0.251 s Press any key to continue.动态规划：回溯法： C:Use rsSa ku raAp pDataXRoam i ngM icrosoftWi nd owsSta rt M en uP ra g ra msCo de Bl c. .要选择的物品是:6Process returned 0 execution time : 0.245 s Press any key to continue.七、 实验分析： 本实验通过贪心算法、动态规划和回溯算法三种算法求解 0-1 背包问题，从 而了解三种算法优缺点。贪心算法 是在当前看来是最好的选择。贪心法在解决问题的策略上目光短浅，只 根据当前已有的信息就做出选择。贪心法并不是从整体最优考虑，它所做出的选择只 是局部最优。 这种局部最优选择并不总能获得整体最优解（ Optimal Solution ），但 通常能获得近似最优解（ Near-Optimal