搜索
贪心算法武松打老虎问题描述：曾经因打虎而闻名的武松在x年后接到了景阳冈动物园的求助信，信上说：最近我们动物园逃跑了几只老虎，请您把它们抓回来，thankyou！武松接到信后立刻上了山。正当他到半山腰是，suddenly！跳出n只猛虎来。每只老虎都有一块虎牌，牌上写着的是每一只虎最大拥有的体力，当武松与老虎PK时，若老虎的体力先用完，那么老虎over，否则武松over。求武松在over之前最多能干掉几只老虎？（注：老虎是一只只上的）输入文件：第一行两个数字n(n50000),t0(武松的体力)。第二行n个数字，分别代表每只老虎的体力。所有变量都不超过longint范围。输出文件：一行，最多能干掉的老虎数。样例输入：610153246样例输出：4分析•题目所求：•最多能干掉的老虎数目•已知武松体力，每只老虎的体力，每干掉一只老虎，都会消耗相应体力。为了干掉更多的老虎每次干掉体力最少的老虎153246老虎体力：123456排序后体力：武松体力10第一轮PK：10-1=9第二轮PK：9-2=7第三轮PK：7-3=4第四轮PK：4-4=0•贪心算法（贪心策略）：•每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。153246老虎体力：当前看来是最好的选择:打死体力最少的老虎！•贪心算法（贪心策略）：•每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。153246老虎体力：武松体力：10打死老虎数目：0•贪心算法（贪心策略）：•每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。153246老虎体力：武松体力：9打死老虎数目：1•贪心算法（贪心策略）：•每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。153246老虎体力：武松体力：7打死老虎数目：2•贪心算法（贪心策略）：•每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。153246老虎体力：武松体力：4打死老虎数目：3•贪心算法（贪心策略）：•每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。153246老虎体力：武松体力：0打死老虎数目：4武松的体力已经不能打死任何一头老虎了，已得到问题的完整解。贪心算法一定能得到最优解吗？要满足以下条件：1、最优子结构；2、贪心选择性质；最优子结构性质(最优化原理)•定义：•当问题的最优解包括了其子问题的最优解时，称该问题具有最优子结构性质。例如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J'是B到C的最优路径，则A到C的路线取I和J'比I和J更优，矛盾。从而证明J'必是B到C的最优路径。(最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。)接下来证明刚才的问题是否具有最优子结构性质最优子结构性质(最优化原理)•定义：•当问题的最优解包括了其子问题的最优解时，称该问题具有最优子结构性质。•每打死一只老虎的体力值为ai，要使打死的老虎总数最多，就要使武松剩下的体力t0-ai能打死更多的老虎。即一个与武松体力t0相关的问题，可以转换为t0-ai体力相关的问题。•体力为t0-ai的是体力为t0的子问题。•体力是t0时的最优解，包括了体力为t0-ai的最优解。•该问题具备最优子结构。最优子结构性质(最优化原理)•定义：•当问题的最优解包括了其子问题的最优解时，称该问题具有最优子结构性质。当武松体力值为t0时打死一只体力值为ai的老虎当武松体力值为t0-ai时子问题最优解A方案最优解B方案此时的最优解此时的最优解包含于若B不包含于A，那么当武松的体力值为t0-ai时，其最优解必定不是B。矛盾。所以，B一定是A的子集。举个栗子153246老虎体力：武松体力10最优解为：打死体力为：1，2，3，4的老虎当打死一只体力为1的老虎后。53246老虎体力：武松体力9最优解为：打死体力为：2，3，4的老虎子集贪心选择性质•定义：•所求问题的整体最优解可以通过一些列局部最优的选择，即贪心选择来达到。•贪心选择：•每次选择剩下的老虎中体力最少的。•武松剩下的体力值越大，能打死的老虎就越多。使用贪心选择（每次选择剩下的老虎中体力最少的），能使武松剩下的体力最大。这种贪心选择，能保证全局最优，即能保证打死最多数量的老虎。•因此具备贪心选择性质。贪心选择性质：所求问题的整体最优解可以通过一些列局部最优的选择，即贪心选择来达到。确定贪心选择方法非常重要！！武松打老虎的贪心选择为：每次选择剩下的老虎中体力最少的。当前看来是最好的选择最大数•题目描述：•设有n个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。•输入描述：•第一行一个正整数n。•第二行n个正整数，空格隔开。•输出描述：•连接成的多位数•样例输入：•Sample1:•3•13312343•样例输出：•Sample1:•34331213分析贪心选择方法方案一：把整数按从大到小的顺序排列起来1331234334331213反例：7234246贪心选择答案：2462374正确答案：7424623方案二：先按每个整数的第一位数字排序，大小相同的再按第二位数字排序，以此类推72342467424623反例：12121贪心选择答案：12112正确答案：12121四个数字第一位分别是7、2、4、2；排列好2个数字（7和4）两个2开头的数比较下一位：3、4246在23之前分析完美方案：先把整数化成字符串，然后再比较a+b和b+a，如果a+bb+a，就把a排在b的前面，反之则把a排在b的后面。如：12123因为：1212312312所以：123在12之前如：12121因为：1211212121所以：12在121之前代码框架intcmp(char*s1,char*s2){比较函数}intmain(){scanf(%d,&n);for(i=1;i=n;i++){读取n个数}{将n个数使用cmp()函数排序}{按排好的顺序输出（中间无空格）}}线段覆盖•题目描述：•在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分（端点可以重合），问最大的k为多少•输入描述：•输入文件的第1行为一个正整数n，下面n行每行2个数字ai，bi，描述每条线段。•输出描述：•输出文件仅包括1个整数，为k的最大值•样例输入：•3•02•24•13•样例输出：•2分析贪心选择方案：每次选取线段右端点坐标最小的线段，保留这条线段，并把和这条线段有公共部分的所有线段删除。重复这个过程，直到任两条线段之间都没有公共部分。因为右端点坐标最小，可以保证所有与这条线段没有公共部分的线段都在这条线段的右边，且所有与这条线段有公共部分的线段两两之间都有公共部分。又根据题意，在这些有公共部分的线段中，最后只能保留一条。显然，右端点坐标最小，对后面线段的影响最小，所以，应保留这条线段。那么，如何证明以上贪心策略的正确性呢每次取左端点坐标最小的行不行？每次取长度最短行不行？均分纸牌•题目描述•有N堆纸牌，编号分别为1，2，…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1堆上取的纸牌，只能移到编号为2的堆上；在编号为N的堆上取的纸牌，只能移到编号为N-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如N=4，4堆纸牌数分别为：①9②8③17④6移动3次可达到目的：从③取4张牌放到④（981310）-从③取3张牌放到②（9111010）-从②取1张牌放到①（10101010）。•输入描述：•第一行N（N堆纸牌，1=N=100）第二行A1A2…An（N堆纸牌，每堆纸牌初始数，l=Ai=10000）•输出描述：•输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。‘•样例输入•4•98176•样例输出：•3分析设a[i]为第i堆纸牌的张数（0=i=n），v为均分后每堆纸牌的张数，s为最小移到次数。按照从左到右的顺序移动纸牌。如第i堆(0in)的纸牌数a[i]不等于平均值，则移动一次(即s加1)，分两种情况移动：（1）若a[i]v，则将a[i]-v张纸牌从第I堆移动到第I+1堆；（2）若a[i]v，则将v-a[i]张纸牌从第I+1堆移动到第I堆；为了设计的方便，我们把这两种情况统一看作是将a[I]-v张牌从第I堆移动到第I+1堆；移动后有：a[I]:=v；a[I+1]:=a[I+1]+a[I]-v；贪心选择：分析我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张纸牌，第二堆剩下-7张纸牌，再从第三堆移动17张到第二堆，刚好三堆纸牌数都是10，最后结果是对的，从第二堆移出的牌都可以从第三堆得到。我们在移动过程中，只是改变了移动的顺序，而移动的次数不变，因此此题使用贪心法是可行的。在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(a[i+1]+a[i]-v0)的情况。如n=3，三堆纸牌数为（1，2，27）这时v=10，为了使第一堆数为10，要从第二堆移9张纸牌到第一堆，而第二堆只有2张纸牌可移，这是不是意味着刚才使用的贪心法是错误的呢？当不具备贪心选择性质时：得到较优解。数字三角•如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。贪心法：7+8+1+7+5=28更优方案：贪心法：更优方案：7+3+8+7+5=30策略：从第一层开始选，每次选择可选的数字中最大的数字第二层选择小些的数目能达到更优解不符合贪心选择性质分析•当不能100%确定一个贪心算法正确时，在使用之前，就应该尝试证明它的不正确性。•要证明其不正确，一种最简单的方法就是举一个反例。•其实，要严格证明一个贪心算法的正确性是很困难的，目前最有效的一种方法叫“矩阵胚理论”，但是很复杂。谢谢