貪心算法之初見課件

貪心算法貪心算法武松打老虎問題描述： 曾經(jīng)因打虎而聞名的武松在x年后接到了景陽(yáng)岡動(dòng)物園的求助信，信上說(shuō)：最近我們動(dòng)物園逃跑了幾只老虎，請(qǐng)您把它們抓回來(lái)，thankyou！武松接到信后立刻上了山。正當(dāng)他到半山腰是，suddenly！跳出n只猛虎來(lái)。每只老虎都有一塊虎牌，牌上寫著的是每一只虎最大擁有的體力，當(dāng)武松與老虎PK時(shí)，若老虎的體力先用完，那么老虎over，否則武松over。求武松在over之前最多能干掉幾只老虎？（注：老虎是一只只上的）輸入文件： 第一行兩個(gè)數(shù)字n(n<50000),t0(武松的體力)。第二行n個(gè)數(shù)字，分別代表每只老虎的體力。所有變量都不超過(guò)longint范圍。輸出文件： 一行，最多能干掉的老虎數(shù)。樣例輸入：610153246樣例輸出： 4武松打老虎問題描述：分析題目所求：最多能干掉的老虎數(shù)目已知武松體力，每只老虎的體力，每干掉一只老虎，都會(huì)消耗相應(yīng)體力。為了干掉更多的老虎每次干掉體力最少的老虎153246老虎體力：123456排序后體力：武松體力10第一輪PK：10-1=9第二輪PK：9-2=7第三輪PK：7-3=4第四輪PK：4-4=0分析題目所求：每次干掉體力最少的老虎153246老虎體力：1貪心算法（貪心策略）：每次都作出在當(dāng)前看來(lái)是最好的選擇，不斷循環(huán)，直到獲得問題的完整解。153246老虎體力：當(dāng)前看來(lái)是最好的選擇:打死體力最少的老虎！貪心算法（貪心策略）：153246老虎體力：當(dāng)前看來(lái)是最好的貪心算法（貪心策略）：每次都作出在當(dāng)前看來(lái)是最好的選擇，不斷循環(huán)，直到獲得問題的完整解。153246老虎體力：武松體力：10打死老虎數(shù)目：0貪心算法（貪心策略）：153246老虎體力：武松體力：10打貪心算法（貪心策略）：每次都作出在當(dāng)前看來(lái)是最好的選擇，不斷循環(huán)，直到獲得問題的完整解。153246老虎體力：武松體力：9打死老虎數(shù)目：1貪心算法（貪心策略）：153246老虎體力：武松體力：9打死貪心算法（貪心策略）：每次都作出在當(dāng)前看來(lái)是最好的選擇，不斷循環(huán)，直到獲得問題的完整解。153246老虎體力：武松體力：7打死老虎數(shù)目：2貪心算法（貪心策略）：153246老虎體力：武松體力：7打死貪心算法（貪心策略）：每次都作出在當(dāng)前看來(lái)是最好的選擇，不斷循環(huán)，直到獲得問題的完整解。153246老虎體力：武松體力：4打死老虎數(shù)目：3貪心算法（貪心策略）：153246老虎體力：武松體力：4打死貪心算法（貪心策略）：每次都作出在當(dāng)前看來(lái)是最好的選擇，不斷循環(huán)，直到獲得問題的完整解。153246老虎體力：武松體力：0打死老虎數(shù)目：4武松的體力已經(jīng)不能打死任何一頭老虎了，已得到問題的完整解。貪心算法（貪心策略）：153246老虎體力：武松體力：0打死貪心算法一定能得到最優(yōu)解嗎？要滿足以下條件：1、最優(yōu)子結(jié)構(gòu)；2、貪心選擇性質(zhì)；貪心算法一定能得到最優(yōu)解嗎？要滿足以下條件：1、最優(yōu)子結(jié)構(gòu)；最優(yōu)子結(jié)構(gòu)性質(zhì)(最優(yōu)化原理)定義：當(dāng)問題的最優(yōu)解包括了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。例如圖2中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設(shè)有另一路徑J'是B到C的最優(yōu)路徑，則A到C的路線取I和J'比I和J更優(yōu)，矛盾。從而證明J'必是B到C的最優(yōu)路徑。(最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。)接下來(lái)證明剛才的問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)(最優(yōu)化原理)定義：例如圖2中，若路線I和J是最優(yōu)子結(jié)構(gòu)性質(zhì)(最優(yōu)化原理)定義：當(dāng)問題的最優(yōu)解包括了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。每打死一只老虎的體力值為ai，要使打死的老虎總數(shù)最多，就要使武松剩下的體力t0-ai能打死更多的老虎。即一個(gè)與武松體力t0相關(guān)的問題，可以轉(zhuǎn)換為t0-ai體力相關(guān)的問題。體力為t0-ai的是體力為t0的子問題。體力是t0時(shí)的最優(yōu)解，包括了體力為t0-ai的最優(yōu)解。該問題具備最優(yōu)子結(jié)構(gòu)。最優(yōu)子結(jié)構(gòu)性質(zhì)(最優(yōu)化原理)定義：每打死一只老虎的體力值為a最優(yōu)子結(jié)構(gòu)性質(zhì)(最優(yōu)化原理)定義：當(dāng)問題的最優(yōu)解包括了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

當(dāng)武松體力值為t0時(shí)打死一只體力值為ai的老虎當(dāng)武松體力值為t0-ai時(shí)子問題最優(yōu)解A方案最優(yōu)解B方案此時(shí)的最優(yōu)解此時(shí)的最優(yōu)解包含于若B不包含于A，那么當(dāng)武松的體力值為t0-ai時(shí)，其最優(yōu)解必定不是B。矛盾。所以，B一定是A的子集。最優(yōu)子結(jié)構(gòu)性質(zhì)(最優(yōu)化原理)定義：當(dāng)武松體力值為t0時(shí)打舉個(gè)栗子153246老虎體力：武松體力10最優(yōu)解為：打死體力為：1，2，3，4的老虎當(dāng)打死一只體力為1的老虎后。53246老虎體力：武松體力9最優(yōu)解為：打死體力為：2，3，4的老虎子集舉個(gè)栗子153246老虎體力：武松體力10最優(yōu)解為：打死體力貪心選擇性質(zhì)定義：所求問題的整體最優(yōu)解可以通過(guò)一些列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。貪心選擇：每次選擇剩下的老虎中體力最少的。武松剩下的體力值越大，能打死的老虎就越多。使用貪心選擇（每次選擇剩下的老虎中體力最少的），能使武松剩下的體力最大。這種貪心選擇，能保證全局最優(yōu)，即能保證打死最多數(shù)量的老虎。因此具備貪心選擇性質(zhì)。貪心選擇性質(zhì)定義：貪心選擇：貪心選擇性質(zhì)：所求問題的整體最優(yōu)解可以通過(guò)一些列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。確定貪心選擇方法非常重要?。∥渌纱蚶匣⒌呢澬倪x擇為：每次選擇剩下的老虎中體力最少的。當(dāng)前看來(lái)是最好的選擇貪心選擇性質(zhì)：確定貪心選擇方法非常重要??！武松打老虎的貪心選最大數(shù)題目描述：設(shè)有n個(gè)正整數(shù)（n≤20），將它們聯(lián)接成一排，組成一個(gè)最大的多位整數(shù)。輸入描述：第一行一個(gè)正整數(shù)n。第二行n個(gè)正整數(shù)，空格隔開。輸出描述：連接成的多位數(shù)樣例輸入：Sample1:313312343樣例輸出：Sample1:34331213最大數(shù)題目描述：分析貪心選擇方法方案一：把整數(shù)按從大到小的順序排列起來(lái)1331234334331213反例：7234246貪心選擇答案：2462374正確答案：7424623方案二：先按每個(gè)整數(shù)的第一位數(shù)字排序，大小相同的再按第二位數(shù)字排序，以此類推72342467424623反例：12121貪心選擇答案：12112正確答案：12121四個(gè)數(shù)字第一位分別是7、2、4、2；排列好2個(gè)數(shù)字（7和4）兩個(gè)2開頭的數(shù)比較下一位：3、4246在23之前分析貪心選擇方法方案一：把整數(shù)按從大到小的順序排列起來(lái)13分析完美方案：先把整數(shù)化成字符串，然后再比較a+b和b+a，如果a+b>b+a，就把a(bǔ)排在b的前面，反之則把a(bǔ)排在b的后面。如：12123因?yàn)椋?2123<12312所以：123在12之前如：12121因?yàn)椋?2112<12121所以：12在121之前分析完美方案：先把整數(shù)化成字符串，然后再比較a+b和b+a，代碼框架intcmp(char*s1,char*s2){比較函數(shù)}intmain(){ scanf("%d",&n);for(i=1;i<=n;i++){讀取n個(gè)數(shù)} {將n個(gè)數(shù)使用cmp()函數(shù)排序} {按排好的順序輸出（中間無(wú)空格）}}代碼框架intcmp(char*s1,char*s2)線段覆蓋題目描述：在一個(gè)數(shù)軸上有n條線段，現(xiàn)要選取其中k條線段使得這k條線段兩兩沒有重合部分（端點(diǎn)可以重合），問最大的k為多少輸入描述：輸入文件的第1行為一個(gè)正整數(shù)n，下面n行每行2個(gè)數(shù)字ai，bi，描述每條線段。輸出描述：輸出文件僅包括1個(gè)整數(shù)，為k的最大值樣例輸入：3022413樣例輸出：2線段覆蓋題目描述：分析貪心選擇方案：每次選取線段右端點(diǎn)坐標(biāo)最小的線段，保留這條線段，并把和這條線段有公共部分的所有線段刪除。重復(fù)這個(gè)過(guò)程，直到任兩條線段之間都沒有公共部分。因?yàn)橛叶它c(diǎn)坐標(biāo)最小，可以保證所有與這條線段沒有公共部分的線段都在這條線段的右邊，且所有與這條線段有公共部分的線段兩兩之間都有公共部分。又根據(jù)題意，在這些有公共部分的線段中，最后只能保留一條。顯然，右端點(diǎn)坐標(biāo)最小，對(duì)后面線段的影響最小，所以，應(yīng)保留這條線段。那么，如何證明以上貪心策略的正確性呢？每次取左端點(diǎn)坐標(biāo)最小的行不行？每次取長(zhǎng)度最短行不行？分析貪心選擇方案：每次選取線段右端點(diǎn)坐標(biāo)最小的線段，保留這條均分紙牌題目描述有N堆紙牌，編號(hào)分別為1，2，…,N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若干張紙牌，然后移動(dòng)。移牌規(guī)則為：在編號(hào)為1堆上取的紙牌，只能移到編號(hào)為2的堆上；在編號(hào)為N的堆上取的紙牌，只能移到編號(hào)為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。例如N=4，4堆紙牌數(shù)分別為：①9②8③17④6移動(dòng)3次可達(dá)到目的：從③取4張牌放到④（981310）->從③取3張牌放到②（9111010）->從②取1張牌放到①（10101010）。輸入描述：第一行N（N堆紙牌，1<=N<=100）第二行A1A2…An（N堆紙牌，每堆紙牌初始數(shù)，l<=Ai<=10000）輸出描述：輸出至屏幕。格式為：所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)?！畼永斎?98176樣例輸出：3均分紙牌題目描述分析設(shè)a[i]為第i堆紙牌的張數(shù)（0<=i<=n），v為均分后每堆紙牌的張數(shù)，s為最小移到次數(shù)。按照從左到右的順序移動(dòng)紙牌。如第i堆(0<i<n)的紙牌數(shù)a[i]不等于平均值，則移動(dòng)一次(即s加1)，分兩種情況移動(dòng)：（1）

若a[i]>v，則將a[i]-v張紙牌從第I堆移動(dòng)到第I+1堆；（2）

若a[i]<v，則將v-a[i]張紙牌從第I+1堆移動(dòng)到第I堆；為了設(shè)計(jì)的方便，我們把這兩種情況統(tǒng)一看作是將a[I]-v張牌從第I堆移動(dòng)到第I+1堆；移動(dòng)后有：a[I]:=v；a[I+1]:=a[I+1]+a[I]-v；貪心選擇：分析設(shè)a[i]為第i堆紙牌的張數(shù)（0<=i<=n），v為均分分析我們繼續(xù)按規(guī)則分析移牌過(guò)程，從第二堆移出9張到第一堆后，第一堆有10張紙牌，第二堆剩下-7張紙牌，再?gòu)牡谌岩苿?dòng)17張到第二堆，剛好三堆紙牌數(shù)都是10，最后結(jié)果是對(duì)的，從第二堆移出的牌都可以從第三堆得到。我們?cè)谝苿?dòng)過(guò)程中，只是改變了移動(dòng)的順序，而移動(dòng)的次數(shù)不變，因此此題使用貪心法是可行的。在從第i+1堆中取出紙牌補(bǔ)充第i堆的過(guò)程中，可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于零(a[i+1]+a[i]-v<0)的情況。如n=3，三堆紙牌數(shù)為（1，2，27）這時(shí)v=10，為了使第一堆數(shù)為10，要從第二堆移9張紙牌到第一堆，而第二堆只有2張紙牌可移，這是不是意味著剛才使用的貪心法是錯(cuò)誤的呢？分析我們繼續(xù)按規(guī)則分析移牌過(guò)程，從第二堆移出9張到第當(dāng)不具備貪心選擇性質(zhì)時(shí)：得到較優(yōu)解。當(dāng)不具備貪心選擇性質(zhì)時(shí)：得到較優(yōu)解。數(shù)字三角如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或得向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。數(shù)字三角如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇貪心法：7+8+1+7+5=28更