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

武松打老虎问题描述曾经因打虎而文明的武松在x年后接到了景阳冈动物园的求助信信上说:最近我们动物园逃跑了几只老虎,请您把它们抓回来thankyou!武松接到信后立刻上了山。正当他到半山腰是suddenly!跳出n只猛虎来。每只老虎都有一块虎牌,牌上写着的是每一只虎最大拥有的体力,当武松与老虎PK时,若老虎的体力先用完,那么老虎over,否则武松over。求武松在over之前最多能干掉几只老虎?(注:老虎是一只只上的)输入文件分别代表每只老虎的体力。所有变量都不超过longint范围。数字,第一行两个数字n(n<50000),t0(武松的体力)。第二行n个输出文件行,最多能干掉的老虎数样例输入153246样例输出分析题目所求:最多能干掉的老虎数目已知武松体力,每只老虎的体力,每干掉一只老虎,都会消耗相应体力。为了干掉更多的老虎每次干掉体力最少的老虎老虎体力武松体力10排序后体力:第一轮PK:10-1=9第二轮PK:9-2=7第三轮PK:7-3=4第四轮PK:44=0贪心算法潘玉斌贪心算法(贪心策略)·每次都作岀在当前看来是最好的选择,不断循环,直到获得问题的完整解。老虎体力:当前看来是最好的选择打死体力最少的老虎!贪心算法(贪心策略)·每次都作岀在当前看来是最好的选择,不断循环,直到获得问题的完整解。老虎体力:武松体力:打死老虎数目:0贪心算法(贪心策略)·每次都作岀在当前看来是最好的选择,不断循环,直到获得问题的完整解。老虎体力:武松体力:打死老虎数目:1贪心算法(贪心策略)·每次都作岀在当前看来是最好的选择,不断循环,直到获得问题的完整解。老虎体力:武松体力:打死老虎数目:2贪心算法(贪心策略)·每次都作岀在当前看来是最好的选择,不断循环,直到获得问题的完整解。老虎体力:武松体力:4打死老虎数目:3贪心算法(贪心策略)·每次都作岀在当前看来是最好的选择,不断循环,直到获得问题的完整解。老虎体力:武松体力:0武松的体力已经不能打死打死老虎数目:4任何一头老虎了,已得到问题的完整解贪心算法一定能得到最优解吗?要满足以下条件:1、最优子结构;2、贪心选择性质;