信息奥林匹克竞赛之贪心算法.ppt

武松打老虎问题描述： 曾经因打虎而文明的武松在x年后接到了景阳冈动物园的求助信，信上说：最近我们动物园逃跑了几只老虎，请您把它们抓回来，thankyou！武松接到信后立刻上了山。正当他到半山腰是，suddenly！跳出n只猛虎来。每只老虎都有一块虎牌，牌上写着的是每一只虎最大拥有的体力，当武松与老虎PK时，假设老虎的体力先用完，那么老虎over，否那么武松over。求武松在over之前最多能干掉几只老虎？〔注：老虎是一只只上的〕输入文件： 第一行两个数字n(n50000),t0(武松的体力)。第二行n个数字，分别代表每只老虎的体力。所有变量都不超过longint范围。输出文件： 一行，最多能干掉的老虎数。样例输入：610153246样例输出： 4

分析题目所求：最多能干掉的老虎数目武松体力，每只老虎的体力，每干掉一只老虎，都会消耗相应体力。为了干掉更多的老虎每次干掉体力最少的老虎老虎体力：排序后体力：武松体力10第一轮PK：10-1=9第二轮PK：9-2=7第三轮PK：7-3=4第四轮PK：4-4=0

贪心算法潘玉斌

贪心算法〔贪心策略〕：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。老虎体力：当前看来是最好的选择:打死体力最少的老虎！

贪心算法〔贪心策略〕：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。老虎体力：武松体力：10打死老虎数目：0

贪心算法〔贪心策略〕：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。老虎体力：武松体力：9打死老虎数目：1

贪心算法〔贪心策略〕：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。老虎体力：武松体力：7打死老虎数目：2

贪心算法〔贪心策略〕：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。老虎体力：武松体力：4打死老虎数目：3

贪心算法〔贪心策略〕：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。老虎体力：武松体力：0打死老虎数目：4武松的体力已经不能打死任何一头老虎了，已得到问题的完整解。

贪心算法一定能得到最优解吗？要满足以下条件：1、最优子结构；2、贪心选择性质；

最优子结构定义：当问题的最优解包括了其子问题的最优解时，称该问题具有最优子结构性质。每打死一只老虎的体力值为ai，要使打死的老虎总数最多，就要使武松剩下的体力t0-ai能打死更多的老虎。即一个与武松体力t0相关的问题，可以转换为t0-ai体力相关的问题。体力为t0-ai的是体力为t0的子问题。体力是t0时的最优解，包括了体力为t0-ai的最优解。该问题具备最优子结构。

老虎体力：武松体力10最优解为：打死体力为：1，2，3，4的老虎当打死一只体力为1的老虎后。老虎体力：武松体力9最优解为：打死体力为：2，3，4的老虎子集

贪心选择性质定义：所求问题的整体最优解可以通过一些列局部最优的选择，即贪心选择来到达。贪心选择：每次选择剩下的老虎中体力最少的。武松剩下的体力值越大，能打死的老虎就越多。使用贪心选择〔每次选择剩下的老虎中体力最少的〕，能使武松剩下的体力最大。这种贪心选择，能保证全局最优，即能保证打死最多数量的老虎。因此具备贪心选择性质。

贪心选择性质：所求问题的整体最优解可以通过一些列局部最优的选择，即贪心选择来到达。确定贪心选择方法非常重要！！武松打老虎的贪心选择为：每次选择剩下的老虎中体力最少的。当前看来是最好的选择

最大数题目描述：设有n个正整数〔n≤20〕，将它们联接成一排，组成一个最大的多位整数。输入描述：第一行一个正整数n。第二行n个正整数，空格隔开。输出描述：连接成的多位数样例输入：Sample1:313312343样例输出：Sample1分析贪心选择方法方案一：把整数按从大到小的顺序排列起来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){比较函数