【精品】算法分析-背包问题

《【精品】算法分析-背包问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二算法实现二一、实验目的与要求熟悉C/C++语言的集成开发环境；通过本实验加深对贪心算法、动态规划和回溯算法的理解。二、实验内容：掌握贪心算法、动态规划和冋溯算法的概念和基木思想，分析并掌握背包问题的三种算法，并分析其优缺点。三、实验题1.”0-1“背包问题的贪心算法2.”0-1“背包问题的动态规划算法3.”0・1”背包问题的回溯算法四、实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、实验程序及运行结果背包问题的贪心算法源程序：#include

2、>#includeusingnamespacestd;structgood//表示物品的结构体doublep;〃价值doublew;〃重車double匸;〃价值与重量的比}a[200];doubles,value,m,result;inti,n;boolbigger(gooda,goodb){returna.r>b.r;}intmain(){printf(n背包问题之贪心算法-n);printfC，输入物品个数scanf(”％d”,&n);〃物品个数printf(”输入物品的重量和价值:n);for(i=0;

3、i

4、print”背包内物品总价值为：％.21f.“,result);//输出结果return0;}运行结果：08u25n6.1<:0・ont价20为c0和；<■to:1量Of濡y数重容忌ke个«-«-品y品口担物an翳背内S入入入包eS厶灵灵弓F530.00.2353445694610233245356508”0・1”背包问题的动态规划算法源程序#include#include#include#includevtime.h>usingnamespacestd;voidKnapsac

5、k(vectorvct_v,vectorvct_w,intc,intn);voidprint(vectorv);voidprintarr(vector>mjntpjntq);voidTraceback(vector>m,vectorvct_w,intcjntn);voidmain(){intmo=10;vectorvct_w;vectorvct_v;intc,n,v,w;cout«n***0-l背包问题Z动态规划***M«end

6、l;cout«n***请输入物品个数***n«endl;cin»n;srand((unsigned)time(NULL));vct_w.push_back(n);〃笫一个位置存放物品个数for(inti=l;i<=n;i++){w=rand()%mo+l;vct_w.push_back(w);}vct_v.push_back(n);for(i=l;i<=n;i++){v=rand()%mo+10;vct_v.push_back(v);}cout«"***请输入背包容暈***"«endkcin»c;coutvv”***请物品重量***n

7、«endl;print(vct_w);cout«n***请输入物品价值***n«endl;print(vct_v);Knapsack(vct_v,vct_w,c,n);}voidprint(vectorv){k)r(inti=l;i>m,intp,intq){fbr(inti二l;iv二p;i++){for(intj=1；jv=q；j++){cout«setw(3)«m[

8、i][j]«"}cout«endl;}cout«endl;}voidKnapsack(vectorvct_w,intc,intn){vector>m(n+1,