用蛮力法、动态规划法和贪心法求解01背包问题

《用蛮力法、动态规划法和贪心法求解01背包问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验项目三用蛮力法、动态规划法和贪心法求解0/1背包问题实验目的1、学会背包的数裾结构的设计，针对不同的问题涉及到的对象的数据结构的设计也不同；2、对0-1背包问题的算法设计策略对比与分析。实验内容：0/1背包问题是给定《个重量为{vvl，w2,...价值为{vl，v2,...，vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。在0/1背包问题中，物品/或者被装入背包，或者不被装入背包，设x/表示物品/装入背包的情况，则当时，表示物品/没有被装入背包，时，表示物品/被装入背包。根据问题的要求，有如下约束条件和

2、目标函数：,Zw'x>-c（式1）x-e{0,1}（1背包的数据结构的设计：typedefstructobject{intn;//物品的编号intw;//物品的重量intv;//物品的价值}wup;wupwpLNj;//物品的数组，N为物品的个数intc;//背包的总重量1、蛮力法蛮力法是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。蛮力法的关键是依次处理所有的元素。用蛮力法解

3、决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们屮找到价值最大的子集。所以蛮力法解0/1背包问题的关键是如何求n个物品集合的所有子集，n个物品的子集有2的n次方个，川一个2的n次方行n列的数组保存生成的子集，以下是生成子集的算法:voidforce(inta[][4])//蛮力法产生4个物品的子集{inti，j;intn=16;intm，t;for(i=0;i<16;i++){t=i;for(j=3;j>=0;j-){m=t%2;a[i][j]=m;t=t/2;

4、for(i=0;i<16;i++)//输出保存子集的二维数组{for(j=0;j<4;j++){printf("%d”，a[i][j]);)printf(MH);}}以下要依次判断每个子集的可行性，找出可行解：voidpanduan(intan[41，intcw[l)////判断每•个子集的可行性，如果可行则计算其价值存•入数组cw，不可行则存入0{inti，j;intn=16;intsw，sv;for(i=0;i<16;i++){sw=0;sv=0;for(j=0;j<4;j++){sw=sw+wp[j].v*a[i][j];sv=sv+w

5、p

6、j].v*alij

7、jj;}if(sw<=c)cw[i]=sv;elsecw[iJ=0;在可行解中找出最优解，即找出可行解中满足目标函数的最优解。以下是找出最优解的算法：intfindmax(intxfl61『41，intcvH)//可行解保存在数组cv屮，最优解就足x数组屮某行的元素值相加得到的最大值{intmax;inti，j;max=O;for(i=0;i<16;i++){if(cv[i]〉max){max=cv[i];參鬱尸；}}printf("最好的组合方案是：”)；for(i=0;i<4;i++){primf("%d"，x

8、j]

9、[i]);returnmax;2、动态规划法动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般來说，子M题的重叠关系表现在对给定闷题求解的递推关系(也就是动态规划函数)中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，W以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。动态规划法设计算法一般分成三个阶段：(1)分段：将原问题分解为若干个相互重叠的子问题；(2)分析：分析fu]题是否满足最优性原理，找出动态规划函数的递推式；(3)求解：利用递推式自底向上计算，实现动态规划过程。0/1

10、背包问题可以看作是决策一个序列(xl，x2,...，.w)，对任一变量h的决策是决定x/=l还是％/=0。在对xf-1决策后，已确定了(xl，...，xf-l)，在决策xf吋，问题处于下列两种状态之一：(1)背包容量不足以装入物品则x/=0,背包不增加价值；(2)背包容量可以装入物品则x/=l,背包的价值增加了v/。这两种情况下背包价值的最大者应该是对xf决策后的背包价值。令表示在前z*(l个物品中能够装入容量为y(1<7

11、wzmax{V(/-l，7),j-vv,)+vj(式4)式3表明：把前而/个物品装入容fi为0的背包和把0个物品装入容量为