蛮力法,动态规划法,贪心法求解背包问题

《蛮力法,动态规划法,贪心法求解背包问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、算法设计与分析实验名称：用蛮力法.动态规划法和贪心法求0/1背包问题作者姓名XXXXXXXXX完成日期：2013年9月22日星期日组的编号：2第一章：简介目录第二章：算法规范数据结构.2伪代码3第三章：算法测试4蛮力法.4动态规划5贪心法5第四章：分析讨论6算法分析.6时间复杂度分析16附录17第二章：算法规范数据结构.2伪代码3第三章：算法测试4蛮力法.4动态规划5贪心法5第四章：分析讨论6算法分析.6时间复杂度分析16附录17声明17第一章：简介问题的描述：0/1背包问题是给定n个重量为{wl,W2,・•・“加、价值为{切,v2,...的物品和一个容量为C

2、的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品i或者被装入背包，或者不被装入背包,设为表示物品i装入背包的情况，则当力=0时，表示物品i没有被装入背包，为=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：VS叫兀°C（式

3、）1=x{e{0,1}（1

4、intv;//物品的价值｝wup;wupwp[N];//物品的数组，N为物品的个数intc;〃背包的总重量第二章:算法规范数据结构：0/1背包问题是给定n个重量为｛wl,w2,…,wn｝＞价值为｛vl,v2,…，vn｝的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中，在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设Xi表示物品i装入背包的情况，则当xi二0时，表示物品i没有被装入背包，xi=l时，表示物品i被装入背包。所以，我们用了数组，函数作为主要的数据结构。用蛮力法、动态规划法和贪心法求解0-1背包问题的算法

5、设计对比与分析。伪代码如下所示一.蛮力法1,1.1,定义物品结构1.2input物品编号，重量，价值2,蛮力法产生了集3,判断子集的可行性4从可行解中找出最优解5输出最优解二、动态规划法1.1定义物品结构wup1.2定义物品输入函数inputwp1.3定义物品输出函数outputwp2,定义函数findmaxvalue3,输入物品4,调用findmaxvalue5,输出结果三.贪心法1.1定义物品结构wup1.2输入物品2,对v/w排序3,输出物品4,选择物品5,计算物品总价值6,输出物品总价值和最优解第三章：测试结果1•蛮力法3.贪心法•'*E:G28p

6、2Debugp2.exe*[青蟹敎据录入方式？[•文徉樓犬2.琏盘输入2请输入物品数量及背包容量410蒲输入:物品名价格重量34567967这个结果没有运行出来，请老师原谅，谢谢。第四章：分析和讨论（一）算法思想分析：1.蛮力法：蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。用蛮力法解决0/1背包问题，需要考虑给定〃个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。所以蛮力法解0/1背包问题的关键是如何求n个物品集

7、合的所有了集，n个物品的了集有2的n次方个，用一个2的n次方行n列的数组保存生成的子集，以下是生成子集的算法：voidforce(inta[]⑷)〃蛮力法产生4个物品的子集{inti,j；intn=16;intm,t;for(i=0;ivl6;i++){t=i;for(j=3;j>=0;j-){m=t%2;a[i][j]=m;t=t/2;}}for(i=0;i<16;i++)〃输出保存子集的二维数组{for(j二0;jv4;j++){printf(n%dn,a[i][j]);printf("n);}以下要依次判断每个子集的可行性，找出可行解：voidpan

8、duan(inta[][4],intcw[])////判断每个了集的可行性，如果可行则计算其价值存入数组cw,不可行则存入0{inti,j;intn=16;intsw,sv;for(i=0;i<16;i++){sw=0;sv=0;for(j=0;jv4;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]=O;}在可行解中找岀最优解，即找岀可行解中满足目标函数的最优解。以下是找出最优解的算法：intfindmax(intx[16][4],intcv[])〃可行

9、解保存在数组cv中，最优解就是X数组中