1、貪心的算法和應(yīng)用，點(diǎn)擊添加文本，點(diǎn)擊添加文本，點(diǎn)擊添加文本，引入貪心的算法，引用1書架(noip-openjudge 4.6算法的貪心)John最近購買了存放奶牛養(yǎng)殖圖書的書架，但書架很快就滿了，只剩下頂面。John共有n頭奶牛(1N20，000)，每頭奶牛都有自己的高度Hi(1Hi10，000)，n頭奶牛的總高度為s。書架高度為b (1bs2，000，007)。為了到達(dá)書架頂部，奶牛可以踩在其他母牛的背上，直到斯特羅漢的整個(gè)高度不低于書架的高度。當(dāng)然，牛越多，危險(xiǎn)就越大。為了幫助約翰到達(dá)書架的頂部，請(qǐng)尋找使用奶牛最少的解決方案。添加文本，單擊添加文本，單擊添加文本，單擊添加文本，定義貪心算法

2、，貪心算法從問題的初始狀態(tài)之一開始，期望通過逐步構(gòu)建面向給定目標(biāo)的最優(yōu)解決方案的方法，創(chuàng)建全球最優(yōu)解決方案。球表示當(dāng)前狀態(tài)。紅色箭頭指示目前的最佳決定。藍(lán)色箭頭表示其他決定。添加點(diǎn)擊文本，添加點(diǎn)擊文本，添加點(diǎn)擊文本，添加點(diǎn)擊文本，貪心算法的特征，選擇貪心標(biāo)準(zhǔn)：選擇貪心標(biāo)準(zhǔn)作為統(tǒng)一標(biāo)準(zhǔn)應(yīng)用當(dāng)前的“最高”標(biāo)準(zhǔn)，以此來應(yīng)用原始問題，但切換到較小的子問題后，每個(gè)步驟似乎都是當(dāng)前最好的選擇。最佳子結(jié)構(gòu)：如果某個(gè)問題的最佳解決方案包含該子問題的最佳解決方案，則該問題具有最佳子結(jié)構(gòu)特性。點(diǎn)擊添加文本，點(diǎn)擊添加文本，點(diǎn)擊添加文本，引入貪心算法，案例2金恩道(noip-openjudge 4.6算法的貪心)一天

3、，KID乘飛機(jī)去了有很多貴重金屬的金恩島。KID喜歡多種寶石的藝術(shù)品，但不拒絕這種珍貴的金屬。但是他只有一個(gè)口袋，口袋最多只能裝重量為w的物品。島金屬有不同重量的s種(n1，n2，ns)，并且每個(gè)金屬的總價(jià)值也是v1、v2、vs。KID一次想拿走最有價(jià)值的金屬，就問能拿走多少有價(jià)值的金屬。注意金屬可以任意分割，金屬的價(jià)值與其重量成正比。點(diǎn)擊添加文本，點(diǎn)擊添加文本，點(diǎn)擊添加文本，點(diǎn)擊添加文本，貪心算法的功能，有幾種策略可供選擇。(1)每次選擇價(jià)值最大的東西時(shí)，把東西放在背包里得到的結(jié)果是最佳的嗎？(2)選擇重量最小的東西時(shí)，能在裝貨地點(diǎn)得到最佳的解決方案嗎？(？(3)每次選擇單位重量值最大的項(xiàng)目

4、時(shí)。添加文本，單擊添加文本，單擊添加文本，單擊添加文本，貪心算法的功能，故障排除一般步驟： 1，設(shè)計(jì)數(shù)據(jù)搜索規(guī)則；2、貪心的推測(cè)；3、準(zhǔn)確證明(嚴(yán)格證明和一般證明)一般證明：列舉反例；嚴(yán)格證明：數(shù)學(xué)劉濤和反證法；4、程序?qū)嵤?。單擊添加文本，單擊添加文本，單擊添加文本，單擊添加文本，?shí)戰(zhàn)案例，銷售人員(NOIP2015入門級(jí)團(tuán)隊(duì)4號(hào))電池壽命(渴望openjudge 4.6算法)，單擊添加文本，單擊添加文本，單擊添加文本，實(shí)際戰(zhàn)斗示例問題，實(shí)際戰(zhàn)斗示例螺絲街是出口等于入口的死胡同，街的一邊是墻，另一邊是房東。螺絲街共n戶，從I戶到入口的距離是Si米。同一幢房子可以有多個(gè)家具，所以入口同一條街上可

5、以有多個(gè)家具。阿明從入口進(jìn)來，依次向NASA的x家銷售產(chǎn)品，然后再走原來的路。胺每走一米累計(jì)一分疲勞值，一戶銷售產(chǎn)品累計(jì)a分疲勞值。工作狂阿明想知道在不對(duì)其他x過度上路的情況下，能積累多少疲勞值。實(shí)際戰(zhàn)斗示例，輸入格式第一行有正整數(shù)n，表示螺釘距離家具的數(shù)量。下一行包含n個(gè)正整數(shù)。其中，第I個(gè)整數(shù)Si表示從假設(shè)I到入口的距離。數(shù)據(jù)保修S1S2Sn108。下一行包含n個(gè)正整數(shù)。其中，第I整數(shù)Ai表示向I家具銷售產(chǎn)品時(shí)累積的疲勞值。數(shù)據(jù)保證Ai103。輸出格式輸出n行，每行有一個(gè)正整數(shù)，I行整數(shù)表示X=i時(shí)累積最大的疲勞值。實(shí)際戰(zhàn)斗范例，輸入范例1 5 1 2 3 4 2 3 4 5，輸出范例1

6、15 19 22 24 25，s 1 2 3 4 5，a 1 2 3 4 5，開始，疲勞值3 6 9 12 15，實(shí)際戰(zhàn)斗范例，輸入范例1 5 1 2 3 4 1 2 a 1 2 3 4 5，開始，疲勞值1 2 3 4，實(shí)際戰(zhàn)斗范例，輸入范例15 1 2 3 4 1 2 3 4 5，輸出范例1 15 19 22 24，s 1 2 3 4 5，A 1 2 3 4 5 輸出范例1 15 19 22 24 25，s 1 2 3 4 5，a 1 2 3 4 5，開始，疲勞值1 2，實(shí)際戰(zhàn)斗范例，輸入范例1 5 1 2 3 4 1 2 3 4 5，輸出范例1 15 19 22 24 25 輸入范例25

7、1 2 4 5 4 5 4 3 4 1，輸出范例2 12 17 21 24 27，疲勞值7 8，7 12 11，實(shí)際戰(zhàn)斗范例，輸入范例2 5 2 4 5 4 5 4 3 4 1，輸出范例2 12 17 21 24 27，s 1 2，2 5 1 2 4 5 3 4 1，輸出范例2 12 17 21 24 27，s 1 2，2 4 5，a 5 4，3 4 1，開始，疲勞值4，3，3，實(shí)際戰(zhàn)斗范例，范例2輸入5 1 2 4 輸入范例25 1 2 4 5 4 4 3 4 1，輸出范例2 12 17 21 27，s 1 2，2 4 5，5，5 4，3 4 1，開始，疲勞值3，加入按一下文字， 添加點(diǎn)擊文

8、本，討論，示例2電池壽命(noip-openjudge 4.6算法的貪心)小s購買了兩個(gè)5號(hào)電池供電的手持游戲機(jī)。 為了長時(shí)間玩游戲，我買了很多5號(hào)電池，因?yàn)檫@些電池的質(zhì)量因制造商而異，所以壽命不同，只能使用5小時(shí)或3小時(shí)。如果只有2個(gè)電池可以使用5小時(shí)1小時(shí)3小時(shí)，那么只能玩3小時(shí)游戲，其他1個(gè)電池不能使用，但是如果有3個(gè)電池可以使用3小時(shí)、3小時(shí)、5小時(shí)，那么用5小時(shí)可用的電池替換3小時(shí)、30分鐘，其中1個(gè)就可以更好地利用。2小時(shí)30分鐘后，用剛更換的電池更換剩下的一臺(tái)電池(該電池還可用2.5小時(shí))，這樣就可以使用，不會(huì)浪費(fèi)5.5小時(shí)。尋找目前已知的電池?cái)?shù)量，以及電池可用的時(shí)間，以盡可能長

9、的方式使用。討論，輸入包含多個(gè)數(shù)據(jù)集。每個(gè)數(shù)據(jù)集由一個(gè)整數(shù)N (2N1000)表示電池?cái)?shù)，N正整數(shù)表示電池使用時(shí)間。輸出為每個(gè)數(shù)據(jù)集輸出一行，表示電池可用的時(shí)間，保留到小數(shù)點(diǎn)后一位。示例輸入2 3 5 3 5 5示例輸出3.0 5.5，討論，情況1:討論，情況2:討論，readln(n)；max 3360=-maxlongint；sum 3360=0；for I :=1 to n do begin read(x)；sum 3360=sum x；if xmax then max :=x；EndReadlnsum :=sum-max；if summax then writeln(sum max)/233603333001)else writeln(sum * 1.