主题Greedymethod.ppt
《主题Greedymethod.ppt》由会员分享,可在线阅读,更多相关《主题Greedymethod.ppt(37页珍藏版)》请在三一文库上搜索。
1、1,主題: Greedy method,解題技巧 什麼是 greedy method? 什麼時候用 greedy method? 類題討論 例題講解: I.96.2.1 歷年題目,2,什麼是 greedy method?,在每次要做選擇時,總是做當時看起來最有利的選擇 (希望可以藉此獲得最終的最佳結果),3,什麼時候用 greedy method?,當問題有下列兩性質時可用 greedy method 解題 Greedy-choice property: global 的最佳化可由 local 的最佳化來得到(也是 greedy method 和 DP 不同之處) Optimal substr
2、ucture: 大問題的最佳解包含將大問題切開後之小問題的最佳解,4,Problem: Knapsack problem,給 n 個物體,每個物體的重量 wi 以及價值 vi,背包的容量 C 選擇一些物體放入背包中,得到最大的價值 0-1 knapsack problem 每個物體只可選擇”放”或”不放” branch&bound wi,vi,C 為整數時可用 DP fractional knapsack problem 物體可切割放入背包,5,解法: Fractional,從單位價值最大的開始放入,依次放到物品放完,或是背包塞滿為止 Sort vi/wi 依 vi/wi 由大到小的次序依序放
3、入物體,10,$60,珠寶,20,$100,黃金,30,$120,不鏽鋼,vi/wi = 6 5 4,50,kanpsack,10,20,20/30,cost = 240,6,Greedy-choice property: 每次總是選單位價值最高的放入 Optimal substructure: 放完珠寶後的選法(黃金 20,不鏽鋼 20),等於一開始沒有任何珠寶,且背包空間變小為 40 的選法,7,Problem: 排活動問題,有一個場地, n 個活動,每個活動各有起始日期 si 及結束日期 fi 找出一個可排入最多活動的排法,0 1 2 3 4 5 6 7 8 9 10 11 12 13
4、14,8,解法,sort fi (由小到大) 依照 fi 由小到大的次序,只要沒有衝突就排入 (如何檢查?),0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,9,證明,令活動依照 fi sort 完的順序為 A = a1, a2, , an 存在一組最佳解包含 a1 若 Y = y1, y2, , yk 是最佳解,則 Y y1 a1 仍是最佳解,Y =,10,令 Y = a1 Y 是最佳解,則 Y 是對 A = ai| si f1 的最佳解,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14,A,11,Problem: H.90.5,給 n 個水果, n
5、 150 , 及每個水果的重量 Wi,150 Wi 240 且 Wi 為整數 將所有水果分成三級,使得所有水果與該級平均值的差距總合最小,12,8 180 160 240 150 200 210 170 230,Sample input,Sample output,2, 235.000 2, 205.000 4, 165 60.000,Sample input/output,水果總數,水果重量,最重組的水果個數及平均,水果與該及平均值差距總合,13,解法,將所有水果依重量排序 可能分級的方式,必定是將整個排序後的序列分成兩段 O(n3) 註: 若分為 k3 級,可考慮 DP,150 160 1
6、70 180 200 210 230 240,14,Problem: A.10020,給 n 個線段的左右端點 Li,Ri 給 M,求最少的線段個數,使得這些線段可以蓋住 0M,並印出這些線段(依 Li 的遞增次序),15,2 1 -1 0 -5 -3 2 5 0 0 1 -1 0 0 1 0 0,Sample input,Sample output,0 1 0 1,Sample input/output,test case 的組數,M,線段的左右端點,第一組輸入結束,需要的線段數,線段的左右端點,16,解法,將所有線段依左端點由小到大排序(平手時,以右端點由小到大決定) 每次選擇 左端點 要
7、覆蓋線段的左端點 且右端點最右的線段 更新要覆蓋線段的左端點為新增線段的右端點,若整個線段已被覆蓋,則停止 證明方式與選活動問題同,17,Problem: 大甲.00.3,給一個 n( 10) 維的 star graph,以及圖上的兩點,求兩點間的最短距離 star graph 上, 點 (x1, x2 , xn) 的鄰居有 (x2, x1 , xn), (x3, x2 , x1, xn), , (xn, x2 , x1) 大甲題庫: http:/www2.nsysu.edu.tw/contest2004/,18,4 1234 4231 1234 3124 2341 1324 3214 421
8、3 3214 2143,Sample input,Sample output,1 2 2 1 3,Sample input/output,star graph 的維度,最小距離,兩點上的值,19,解法,令起點為 X = (x1, x2, , xn),終點為 Y = (y1, y2, , yn) 每次看 x1 在 Y 中的位置為何 (假設在 j),將 x1 與 xj 交換,重複動作直到相等為止,20,Problem: H.91.5,給定一個長度為 N (10 N 100)的整數數列,從裡面找出一段位置連續且總合最大的數字,並輸出總合及這段連續數字。若有一段以上的數字同時有最大的總合,則挑選長度最
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 主题 Greedymethod
链接地址:https://www.31doc.com/p-2714438.html