1、ACM程序設(shè)計競賽入門，浙江工業(yè)大學(xué)田賢忠2020/7/30，1，2020/7/30，2，第七講，貪心算法（貪婪算法)，2020/7/30，3，什么是貪心算法？2020/7/30，4，所謂貪心算法 :在對問題求解時，采用逐步構(gòu)造最優(yōu)解。也就是說，它要求貪心地選擇最佳操作，并希望通過一系列局部的最優(yōu)選擇，能夠產(chǎn)生一個整個問題的（全局（最優(yōu)解。決策一旦作出，就不能更改。作為貪婪決策的依據(jù)稱為貪心準(zhǔn)則（貪婪標(biāo)準(zhǔn))，2020/7/30，5，一個簡單例子，F(xiàn)atMouse Trade，2020/7/30，6，HDOJ: 1009FatMouse Trade，2020/7/30，7，問題描述FatMous

2、e準(zhǔn)備了M磅貓糧，準(zhǔn)備與看守倉庫的貓進(jìn)行交易，倉庫里有他最喜歡的食物JavaBean .倉庫有N個房間。第一個房間里有幾磅的JavaBeans，需要幾磅的貓糧FatMouse .并不需要用房間里所有的JavaBeans來交換，相反，如果他支付一磅貓糧，他可能會得到一磅JavaBeans .這里a是一個實數(shù)?，F(xiàn)在他給你布置了這個作業(yè)，告訴他他能獲得的最大數(shù)量的JavaBeans .2020/7/30，8，輸入：輸入由多個測試用例組成。每個測試用例以包含兩個非負(fù)整數(shù)M和N的一行開始，然后是N行，每一行分別包含兩個非負(fù)整數(shù)紀(jì)和Fi .最后一個測試用例后面是兩個1 .所有整數(shù)都不大于1000 .輸出：

3、對于每個測試用例，在一行中打印一個精確到小數(shù)點后3位的實數(shù)，這是FatMouse可以獲得的最大JavaBeans數(shù)量2007年.樣本輸入5 3 (5個，有3個交換的地方)7 2 (2換7) 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1，樣本輸出13.333 31.500，2020/7/30，9，貪心準(zhǔn)則：很明顯，每次總是先挑最劃算的交易，一直把手里的貓糧都換完，2020/7/30，10，算法基本思想：輸入（其中，交易數(shù)據(jù)j，F(xiàn)對放入數(shù)組（對數(shù)組排序（按效益，降序（按效益高低進(jìn)行有序交易，一直把手里的貓糧都換完。輸出得到的爪哇豆2020年7月30日，11，部分參考代碼：結(jié)構(gòu)、倉庫、豆類、食品；雙r；a1001號倉庫；2020/7/