kok电子竞技

1、用贪心算法求解背包问题D 软件 101 薛思雨 511020825一、贪心算法介绍顾名思义， 贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最 优考虑， 它所作出的选择只是在某种意义上的局部最优选择。当然， 希望贪心算法得到的最终结果也是整体最优的。 虽然贪心算法不能对所有问题都得到整体最优解， 但对许多问题它 能产生整体最优解。 如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算 法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求解的问题一般具有两个重要性质： 贪心选择性质和最优子结构性质。 所谓贪 心选择性质是指所求问题的整体最优解可以通过一系

2、列局部最优解的选择， 即贪心选择来达 到。 这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质。 问题的最优子结 构性质是该问题可用动态规划算法或贪心算法求解的关键特征。二、贪心法的基本思路从问题的某一个初始解出发逐步逼近给定的目标， 以尽可能快的地求得更好的解。 当达 到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。三、关于贪心算法在背包问题中的应用的探讨 问题描述：0-1

3、 背包问题：给定 n 种物品和一个背包。物品 i 的重量是 Wi ，其价值为 Vi ，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时， 对每种物品 i 只有 2 种选择，即装入背包 (1)或不装入背包 (0)。不能将物品 i 装入背包 多次，也不能只装入部分的物品 i。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，K i < n。 贪心算法解决背包问题有几种策略：(i) 一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装

4、入(假设有足够容量) ，然后是下一个价值最大的物品，如此 继续下去。 这种策略不能保证得到最优解。 例如， 考虑 n=2, w=100,10,10, p =20,15,15, c = 105。当利用价值贪婪准则时，获得的解为x= 1 , 0 , 0 ，这种方案的总价值为 2 0。而最优解为 0 , 1 , 1 ，其总价值为 3 0。(ii) 另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽 然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=10,20, p=5,100, c= 2 5 。当利用重量贪婪策略时， 获得的解为

5、x =1,0, 比最优解 0 , 1要差。(iii) 还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si, 即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能 的多放，直到装满背包。有的参考资料也称为价值密度 pi/wi 贪婪算法。这种策略也不能保证得到最优解。利用此策 略试解 n= 3 ,w=20,15,15, p=40,25,25, c=30 时的最优解。虽然按 pi /wi 非递(增)减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。而且这是解决普通背包问题的最优解，因为在选择物品 i 装入背包时，可以选择物品

6、i 的一容量跳出部分，而不一定要全部装入背包，K i < n。 贪心算法解决背包问题的算法实现： #include "iostream" using namespace std;struct goodinfofloat p; / 物品效益 float w; / 物品重量 float X; / 物品该放的数量 int flag; / 物品编号;/ 物品信息结构体void Insertionsort(goodinfo goods,int n)int j,i; for(j=2;j<=n;j+) goods0=goodsj; i=j-1;while (goods0.p&

7、gt;goodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0;/ 按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n)float cu; int i,j; for(i=1;i<=n;i+) goodsi.X=0;cu=M; / 背包剩余容量 for(i=1;i<n;i+)if(goodsi.w>cu)/ 当该物品重量大与剩余break; goodsi.X=1; cu=cu-goodsi.w;/ 确定背包新的剩余容 if(i<=n) goodsi.X=cu/goodsi.w;/ 该

8、物品所要放 的量/按物品编号做降序排列 for(j=2;j<=n;j+) goods0=goodsj; i=j-1;while (goods0.flag<goodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout<<" 最优解为 :"<<endl;for(i=1;i<=n;i+)coutvv"第"vvivv"件物品要放："；cout<<goodsi.X<<endl;int main(void)coutvv"| 运 用

9、 贪 心 法 解 背 包 问 题|"vvendl；coutvv"|"vvendl；int i,j,n；float M；goodinfo *goods； /定义一个指针 coutvv"press v1> to run the program"vvendl； coutvv"press v0> to exit"vvendl； cin>>j；while(j)coutvv"请输入物品的总数量："cin>>n；goods=new struct goodinfo n+1; coutv

10、v"请输入背包的最大容量：" cin>>M;coutvvendl;for(i=1;iv=n;i+)goodsi.flag=i;coutvv"请输入第"vvivv"件物品的重 量："cin>>goodsi.w; coutvv"请输入第"vvivv"件物品的效 益："cin>>goodsi.p; goodsi.p=goodsi.p/goodsi.w; / 得出物品的效益，重量比coutvvendl;Insertionsort(goods,n); bag(goods

11、,M,n);coutvv"press v1> to run agian"vvendl;cout<v"press <0> to exit"«endl; cin>>j;system("pause"); return 0;rcss <03 to exitress <1 > ta i*«ina<jianfods忙Ci ruripxiDress <0> to exit11 D:XX乍9G时sDEV93MYPROJ ECTStanxinDeb号店nx n,己壮的的 SS 1 1 葺肆 入入I 土H青四、结果分析：对于0-1背包问题，贪心算法之所以不能得到最优解是因为在这种情况下，它无法保证最后能将背包装满，部分闲置的背包空间，使每公斤背包的价值降低了。以上算法的时间复杂度和空间复杂度为O(n*n)，其中时间复杂度基本已经不能再优化了，但空间复杂度可以优化到O(n)。