【正文】 和齊王最快的馬比，輸一場，因為反正要輸一場，不如拿最沒用的馬輸。 ? 當田忌最快的馬和齊王最快的馬相等時，這就要展開討論了 ,貪心方法是，拿最慢的馬來和齊王最快的馬比 . 電池的壽命 ? 小 S新買了一個掌上游戲機，這個游戲機由兩節(jié) 5號電池供電。為了保證能夠長時間玩游戲，他買了很多 5號電池，這些電池的生產(chǎn)商不同，質(zhì)量也 有差異，因而使用壽命也有所不同，有的能使用 5個小時，有的可能就只能使用 3個小時。顯然如果他只有兩個電池一個能用 5小時一個能用 3小時，那么他只能玩 3個小時的游戲，有一個電池剩下的電量無法使用，但是如果他有更多的電池，就可以更加充分地利用它們，比如他有三個電池分別能用 5小時，他可以先 使用兩節(jié)能用 3個小時的電池，使用半個小時后再把其中一個換成能使用 5個小時的電池，兩個半小時后再把剩下的一節(jié)電池換成剛才換下的電池（那個電池還能用 ），這樣總共就可以使用 ，沒有一點浪費。 現(xiàn)在已知電池的數(shù)量和電池能夠使用的時間，請你找一種方案使得使用時間盡可能的長。 思路 ? 設(shè)最大的電池電量為 x 其余的電量和為 S ? 如果 x=S 。 ans=2*S 這個好理解 ? 否則 ans=x+S 思路 ? 當 xS 時我們?nèi)? 最大的兩個電池進行消耗 ? 消耗到他們不是最大的為止 此時 xS ? 重復進行前兩步則 S必然趨于 0 故 x趨于 0 ? 所以可以全部消耗 活動安排問題 ? 設(shè)有 n個活動的集合 e={1， 2， … ， n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動 i都有 一個要求使用該資源的起始時間 si和一個結(jié)束時間 fi,且 sifi。如果選擇了活動 i，則它在半開時間區(qū)間 [si， fi]內(nèi)占用資源。若區(qū)間 [si， fi]與區(qū)間 [sj， fj]不相交，則稱活動 i與活動 j是相容的。也就是說，當 si≥fi或 sj≥fj時，活動 i與活動 j相容?；顒影才艈栴}就是 要在所給的活動集合中選出最大的相容活動子集合。 設(shè)待安排的 11個活動的開始時間和結(jié)束時間按結(jié)束時間的 非減序排列如下： i 1 2 3 4 5 6 7 8 9 10 11 Starti 1 3 0 5 3 5 6 8 8 2 12 Endi 4 5 6 7 8 9 10 11 12 13 14 算法的計算過程如下圖所示。圖中每行相應于算法的一次迭代。 陰影長條表示的活動是已選入集合的活動，而空白長條表示的活 動是當前正在檢查相容性的活動。 貪心 ? 我們先證明 排序后的第一個活動一定在解集中 ? 假設(shè)我們有一個最有解 A 他不包含 活動 1 ? 那么我們必然可以將 A中 end時間最早的替換成 活動 1 ? 得證 ? 以此類推，可以證明貪心算法的最優(yōu)性 旅行家的預算 ? 一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱是空的）。給定兩個城市之間的距離 D汽車郵箱的容量 C（以升為單位）。每升汽油能行使距離 D出發(fā)點的每升汽油價格 P和沿途油站數(shù)（ N可以是 0）、油站 I離出發(fā)點的距離 Di、油站 I每升汽油價格 Pi（ I=1,2,3…… N）。 ? 編程找出一種加油方案，使費用最少，輸出這個最少的費用值，計算結(jié)果四舍五入至小數(shù)點后兩位。如果無法到達目的地，則輸出 “ No Solution”。 旅行家的預算 ? 我們可以假設(shè)每次都裝滿油箱，只有當要用油時才對其付款。 ? 可以很明確的看到，但我們發(fā)現(xiàn)油箱里的油比當前可以買的油貴時，就用便宜的油來替代，這樣一定最優(yōu)。 貪心算法的基本要素 ? 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢 ?這個問題很難給予肯定的回答。 ? 但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有 2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 貪心選擇性質(zhì) ? 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 ? 動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。 ? 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。 最優(yōu)子結(jié)構(gòu)性質(zhì) ? 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 Bridge ? n個人要過河，有一橋，一盞燈，每次橋上可以過兩人，但是一定要帶燈。 ? 現(xiàn)給出 n個人過橋時間，問最短時間可以過完橋。 Bridge ? 當人數(shù)等于 1， 2， 3的時候：答案很容易得出； ? 當人數(shù)大于等于 4時： ? 若設(shè)過橋速度最快的那個人過橋時間為 a,第二快為b。過橋第二慢的那個人過橋時間為 y,最慢為 z。 ? 此時有兩種過橋方案： ? 最快和次快的人先過，然后最快的回來，然后最慢與次慢的人再過，次快的回來； ? 最快的和最慢的過，快的回來，在和次慢的過，快的再回來； Bridge ? 第一種方法時間為 b*2+a+z ? 第二種方法時間為 y+z+2*a ? 如果第一種大于第二種 有 2*b+a+zy+z+2*a ? 化簡得 ? 2*by+a。 ? 此時只要比較 2*b和 a+y的大小即可知道那種方法更優(yōu) ? 每次遵循局部最優(yōu)策略即可 最優(yōu)數(shù)對 ? 按遞增的順序告訴你 N個正整數(shù)和一個實數(shù)P，要求求出求出該數(shù)列中的比例最接近 P的兩個數(shù)（保證絕對沒有兩個數(shù)使得其比值為 P）。 最優(yōu)數(shù)對 ? 定義兩個指針 i和 j，然后進行如下操作：當code[j]/code[i]p時 i++，當 code[j]/code[i]p時 j++，然后記錄其中產(chǎn)生的最優(yōu)值即可。 連續(xù)數(shù)之和最大值 ? 給你 N個數(shù)，要求求出其中的連續(xù)數(shù)之和的最大值 連續(xù)數(shù)之和最大值 ? 定義一個統(tǒng)計變量 tot， 然后用循環(huán)進行如下操作 ： tot+=item 其中如果出現(xiàn) tot0的情況，則將 tot賦值為 0。在循環(huán)過程之中 tot出現(xiàn)的最大值即為答案。