资源描述:
《蛮力法,动态规划法,贪心法求解背包问题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、实验名称:用蛮力法、动态规划法和贪心法求0/1背包问题组的编号:28作者姓名:xxxxxxxxx算法设计与分析完成日期:2013年9月22日星期日目录第一章:简介1第二章:算法规范2数据结构2伪代码3第三章:算法测试4蛮力法4动态规划5贪心法5第四章:分析讨论6算法分析6时间复杂度分析16附录17声明17第一章:简介问题的描述:0/1背包问题是给定n个重量为{w1,w2,…,wn}、价值为{v1,v2,…,vn}的物品和一个容量为C的背包,求这些物品中的一个最有价值的子集,并且要能够装到背包中。在0/1背包问题中,物品i或者被装入
2、背包,或者不被装入背包,设xi表示物品i装入背包的情况,则当xi=0时,表示物品i没有被装入背包,xi=1时,表示物品i被装入背包。根据问题的要求,有如下约束条件和目标函数:(式1)(式2)于是,问题归结为寻找一个满足约束条件式1,并使目标函数式2达到最大的解向量X=(x1,x2,…,xn)。背包的数据结构的设计:typedefstructobject{intn;//物品的编号intw;//物品的重量intv;//物品的价值第26页}wup;wupwp[N];//物品的数组,N为物品的个数intc;//背包的总重量第二章:算法规范
3、数据结构:0/1背包问题是给定n个重量为{w1,w2,…,wn}、价值为{v1,v2,…,vn}的物品和一个容量为C的背包,求这些物品中的一个最有价值的子集,并且要能够装到背包中,在0/1背包问题中,物品i或者被装入背包,或者不被装入背包,设xi表示物品i装入背包的情况,则当xi=0时,表示物品i没有被装入背包,xi=1时,表示物品i被装入背包。第26页所以,我们用了数组,函数作为主要的数据结构。用蛮力法、动态规划法和贪心法求解0-1背包问题的算法设计对比与分析。伪代码如下所示一、蛮力法1,1.1,定义物品结构1.2input物品
4、编号,重量,价值2,蛮力法产生子集3,判断子集的可行性4从可行解中找出最优解5输出最优解二、动态规划法1.1定义物品结构wup1.2定义物品输入函数inputwp1.3定义物品输出函数outputwp2,定义函数findmaxvalue3,输入物品4,调用findmaxvalue5,输出结果三、贪心法第26页1.1定义物品结构wup1.2输入物品2,对v/w排序3,输出物品4,选择物品5,计算物品总价值6,输出物品总价值和最优解第三章:测试结果1.蛮力法第26页1.动态规划法3.贪心法第26页这个结果没有运行出来,请老师原谅,谢谢
5、。第四章:分析和讨论(一)算法思想分析:1.蛮力法:蛮力法是一种简单直接的解决问题的方法,常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。用蛮力法解决0/1背包问题,需要考虑给定n个物品集合的所有子集,找出所有可能的子集(总重量不超过背包容量的子集),计算每个子集的总价值,然后在他们中找到价值最大的子集。所以蛮力法解0/1背包问题的关键是如何求n个物品集合的所有子集,n个物品的子集有2的n次方个,用一个2的n次方行n列的数组保存生成的子集,以下是生成子集的算法:voidforce(inta[][4])/
6、/蛮力法产生4个物品的子集{inti,j;intn=16;intm,t;for(i=0;i<16;i++){t=i;for(j=3;j>=0;j--)第26页{m=t%2;a[i][j]=m;t=t/2;}}for(i=0;i<16;i++)//输出保存子集的二维数组{for(j=0;j<4;j++){printf("%d",a[i][j]);}printf("");}}以下要依次判断每个子集的可行性,找出可行解:voidpanduan(inta[][4],intcw[])////判断每个子集的可行性,如果可行则计算其价值存入
7、数组cw,不可行则存入0{inti,j;intn=16;第26页intsw,sv;for(i=0;i<16;i++){sw=0;sv=0;for(j=0;j<4;j++){sw=sw+wp[j].w*a[i][j];sv=sv+wp[j].v*a[i][j];}if(sw<=c)cw[i]=sv;elsecw[i]=0;}在可行解中找出最优解,即找出可行解中满足目标函数的最优解。以下是找出最优解的算法:intfindmax(intx[16][4],intcv[])//可行解保存在数组cv中,最优解就是x数组中某行的元素值相加得到的
8、最大值{intmax;第26页inti,j;max=0;for(i=0;i<16;i++){if(cv[i]>max){max=cv[i];j=i;}}printf("最好的组合方案是:");for(i=0;i<4;i++){printf("%