贪心算法的应用

贪心算法的应用课程名称：算法设计与分析院系：计算机科学与信息工程学院学生姓名：****学号：**********专业班级：**********************************指导教师：******201312-271贪心算法的应用摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。关键词：贪心法背包问题最优化2目录第1章绪论.............................................31.1贪心算法的背景知识................................31.2贪心算法的前景意义................................3第2章贪心算法的理论知识...............................42.1问题的模式........................................42.2贪心算法的一般性描述..............................4第3章背包问题.........................................53.1问题描述..........................................53.2问题分析..........................................53.3算法设计..........................................53.4测试结果与分析...................................10第4章结论............................................12参考文献................................................13附件....................................................133第1章绪论1.1贪心算法的背景知识贪心算法又叫登山法，它的根本思想是逐步到达山顶，即逐步得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。“贪心”可以理解为以逐步的局部最优，达到最终的全局最优。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。一定要注意，选择的贪心策略要有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的决策影响。也就是说某状态以后的过程不会影响以前的状态，至于当前的状态有关，也称这种特性为无后效性。已经学会在解的范围可以确定的情况下，可以采用枚举或递归策略，找出所有的结果，一一比较它们，可能在有限的时间内找不到问题的解。这时可以考虑用贪心的策略，选取那些最可能到达解的情况来考虑。例如为了使生产某一产品所花费的时间最少，一种贪心的策略就是在生产该产品的每一道工序上都选择最省时的方法。所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。1.2贪心算法的前景意义贪心算法的主要思想是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时算法停止。该算法存在问题其一是不能保证求得的最后解是最佳的；其二，不能用来求最大或最小解问题；其三，只能求满足某些约束条件的可行解的范围。所以贪心算法是解决最优化问题时的一种简单但适用范围有限的策4略。贪心算法无后向性在解的范围可以确定的情况下，可以采用枚举或递归策略，找出所有的结果，一一比较它们，可能在有限的时间内找不到问题的解。这时可以考虑用贪心的策略，选取那些最可能到达解的情况来考虑。贪婪算法策略在《数据结构》课程中的算法也有广泛的应用，如霍夫曼树、构造最小生成树的Prim算法和Kruskal算法的决策过程，都是使用的贪婪算法策略。第2章贪心算法的理论知识2.1问题的模式对于背包问题。重量为w1,w2,w3…wn的若干物品和容量为m的背包，物品的价值分别为p1,p2,p3…pn。要求找出这n个物品的一个子集，使其尽可能是选入背包的物品的价值最大，即：最大化：w1+w2+w3+…+wn=m时，也就是如果所选取的货物的总重量小于背包容量就全选进去；但出现了w1+w2+w3+…+wnm时，对物品先进行按单位价值高到低排序，为了不把物品原来的编码打乱，采用一个数组来存放单位价值从大到小的物品的编码即可。所以就只能选取n个货物中的一部分使其总利润最大。2.2贪心算法的一般性描述贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路如下：（1）建立数学模型来描述问题。（2）把求解的问题分成若干个子问题。（3）对每一子问题求解，得到子问题的局部最优解。（4）把子问题的解局部最优解合成原来解问题的一个解。这就是一个用贪婪算法来解决背包问题课题，我们假设每一种货物都可以分成需要的任意小部分放入背包，要求从中取得最大利润。因为每一个物品都可5以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。第3章背包问题3.1问题描述贪心算法解决背包问题：一个商人带着一个能装m千克的背包去乡下收购货物，准备将这些货物卖到城里获利。现在有n种货源，且知道第i中货物有wi千克，可获利pi元。请编写算法帮助商人收购货物，以获取最高的利润。3.2问题分析首先，输入物品的个数和背包的容量，再对所有物品的重量累加如果总重量小于背包的容量，就将所有的物品装入背包；如果大于背包的总容量将这些物品按照单位价值从高到低的顺序进行排序，然后进行选择。并且要求所选物品的最终总量不能超过背包能承受的重量，要求所选的最终方案为最优。3.3算法设计对于本课题我们可一大致分两种情况：当w1+w2+w3+...+wn=m时，选取所有物品即可，得到总的价值；当w1+w2+w3+...+wnm的情况，只能选取一部分货物装入背包，这里假设每一个物品都可以分成任意一小部分，所以利用贪心策略，每次优先选取价值与重量比最大的装入背包，就能获得最高的利润，直到背包刚好装满为止，然后输出必要的数据及结果。在对物品按单位价值从大到小排列的具体实现可以使用快速排列算法，并用p1[max]=0来标记已经进行排列的物品，这样可以使搜索的项越来越少。3.3.1算法分析6因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下：（1）先将单位块收益按从大到小进行排序；（2）初始化背包当前装入量和当前价值；（3）从前到后考虑所有物品：a.如果可以完全放入，当前价值加上物品总价值，背包当前装入量加上物品总体积；b.如果可以部分放进，当前价值加上物品价值*背包剩余体积，以至于背包的剩余体积为0.利用贪心策略解题，需要解决两个问题：（1）确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：a.可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。b.原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。（2）如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。3.3.2数据结构在进行算法设计时为了使数据更容易观察和操作，我们需要设定一些必要的数组等变量。m变量是背包的容量，n是物品的总种类数，pp是装入背包中物品的总价值。W数组来存放输进来的物品的重量，其下标代表物品的编号；P数组存放每7一件物品的价值，同样下标代表物品的编号；P1是P数组的副本是用来在计算中使用的，有可能会改变其中的值；b数组用来存放根据单位价值由大到小排了序的物品的编号；它的下标代表着物品单位价值的大小的次序。比如：b[1]是单位价值最大的物品的编号。再定义一个计算装入背包中的物品的总价值，可以在输出结果时在输出选取物品的编码和重量的同时还可以得到总价值。（1）输入了物品的信息后，对物品的重量累加：for(i=1,s=0;i=n;i++)//算出物品的总重量s{printf(物品的编号:%d\n重量:,i);scanf(%f,&w[i]);printf(价值:);scanf(%f,&p[i]);p1[i]=p[i];s=s+w[i];}（2）如果s=m，就可以得到问题的解并输出得到的总利润：if(s=m)//物品的总重量如果小于m则全装入{for(i=1;i=n;i++)pp+=p[i];printf(选择的结果是:物品的总重量小于背包的容量故全装入背包,得到的总利润是:%f\n,pp);return0;}（3）如果sm时，用选择排序法对物品按单位价值排序：for(i=1;i=n;i++){max=1;for(j=2;j=n;j++)if(p1[j]/w[j]p1[max]/w[max])//比较物品的单位价值max=j;8p1[max]=0;//标记已经排了序的物品b[i]=max;}（4）排好序，再对物品从排了序的数组中连续装入物品直到装入的重量大于m时修改最后一个装入的物品的重量和价值：for(i=1,s=0;sm&&i=n;i++)s=s+w[b[i]];floatw1=w[b[i-1]];if(s!=m)//超出背包容量{w[b[i-1]]=m-(s-w[b[i-1]]);//装入第b[i-1]个物品的重量p[b[i-1]]=w[b[i-1]]/w1*p[b[i-1]];//装入第b[i-1]个物品的价值}（5）输出最后的结果：for(j=1;j=i-1;j++)//输出选取的结果{printf(物品的编号:%d,可装入该物品的重量:%f\n,b[j],w[b[j]]);pp+=p[b[j]];}printf(总价值%f\n,pp);//装入背包的物品的总价值93.3.3流程图开始输入m,,n输入物品的重和价值所有物品总重s=s+w[i]S=mmmYNpp=pp+p[i]所有物品价值输出结果比较物品单位价值并得出序列数组b[]按b[]装物品s=s+w[b[i]]w1=w[b[i-1]]NSmW[b[i-1]]=m-(s-w[b[i-1]])P[b[i-1]]=w[b[i-1]]/w1*p[b[i-1]]Ypp=pp+p[b[j]]输出总价值结束10图3-1流程图3.4测试结果与分析测试结果：************