- 1、本文档共37页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
主题Greedmethod
主題: Greedy method 解題技巧 什麼是 greedy method? 什麼時候用 greedy method? 類題討論 例題講解: I.96.2.1 歷年題目 什麼是 greedy method? 在每次要做選擇時,總是做當時看起來最有利的選擇 (希望可以藉此獲得最終的最佳結果) 什麼時候用 greedy method? 當問題有下列兩性質時可用 greedy method 解題 Greedy-choice property: global 的最佳化可由 local 的最佳化來得到(也是 greedy method 和 DP 不同之處) Optimal substructure: 大問題的最佳解包含將大問題切開後之小問題的最佳解 Problem: Knapsack problem 給 n 個物體,每個物體的重量 wi 以及價值 vi,背包的容量 C 選擇一些物體放入背包中,得到最大的價值 0-1 knapsack problem 每個物體只可選擇”放”或”不放” branchbound wi,vi,C 為整數時可用 DP fractional knapsack problem 物體可切割放入背包 解法: Fractional 從單位價值最大的開始放入,依次放到物品放完,或是背包塞滿為止 Sort vi/wi 依 vi/wi 由大到小的次序依序放入物體 Greedy-choice property: 每次總是選單位價值最高的放入 Optimal substructure: 放完珠寶後的選法(黃金 20,不鏽鋼 20),等於一開始沒有任何珠寶,且背包空間變小為 40 的選法 Problem: 排活動問題 有一個場地, n 個活動,每個活動各有起始日期 si 及結束日期 fi 找出一個可排入最多活動的排法 解法 sort fi (由小到大) 依照 fi 由小到大的次序,只要沒有衝突就排入 (如何檢查?) 證明 令活動依照 fi sort 完的順序為 A = {a1, a2, …, an} 存在一組最佳解包含 a1 若 Y = {y1, y2, …, yk} 是最佳解,則 Y – {y1}?? {a1} 仍是最佳解 令 Y = {a1} ? Y’ 是最佳解,則 Y’ 是對 A’ = {ai| si f1} 的最佳解 Problem: H.90.5 給 n 個水果, n ? 150 , 及每個水果的重量 Wi,150 ? Wi ? 240 且 Wi 為整數 將所有水果分成三級,使得所有水果與該級平均值的差距總合最小 Sample input/output 解法 將所有水果依重量排序 可能分級的方式,必定是將整個排序後的序列分成兩段 O(n3) 註: 若分為 k3 級,可考慮 DP Problem: A.10020 給 n 個線段的左右端點 Li,Ri 給 M,求最少的線段個數,使得這些線段可以蓋住 [0..M],並印出這些線段(依 Li 的遞增次序) Sample input/output 解法 將所有線段依左端點由小到大排序(平手時,以右端點由小到大決定) 每次選擇 左端點 ? 要覆蓋線段的左端點 且右端點最右的線段 更新要覆蓋線段的左端點為新增線段的右端點,若整個線段已被覆蓋,則停止 證明方式與選活動問題同 Problem: 大甲.00.3 給一個 n(? 10) 維的 star graph,以及圖上的兩點,求兩點間的最短距離 star graph 上,點 (x1, x2 ,…, xn) 的鄰居有 (x2, x1 ,…, xn),(x3, x2 , x1…, xn),…,(xn, x2 ,…, x1) 大甲題庫: .tw/contest2004/ Sample input/output 解法 令起點為 X = (x1, x2, …, xn),終點為 Y = (y1, y2, …, yn) 每次看 x1 在 Y 中的位置為何 (假設在 j),將 x1 與 xj 交換,重複動作直到相等為止 Problem: H.91.5 給定一個長度為 N (10 ? N ? 100)的整數數列,從裡面找出一段位置連續且總合最大的數字,並輸出總合及這段連續數字。若有一段以上的數字同時有最大的總合,則挑選長度最短的那一段。 Input File / Output File None (91年沒有放出test case) Sample Input/Output Sample input: N 行數字(每個數字的範圍在 -50 ~ 50 之間) Sample output:81, 4, -3, 6 直覺解法 任選兩個位置 i, j (i j),令 i 為起點,j 為終點,就可
您可能关注的文档
- 中国钢铁结构股份有公司董事会议事规则.PDF
- 中国银行业改革两难外资作用.ppt
- 中国连锁节东京分会全球技术转移体验之旅(日本).PDF
- 中国银行省行本部驾服务外包.doc
- 中国青年政治学2016届毕业生就业质量年度报告.PDF
- 中国阅读报告·香社会目录.PDF
- 中国音乐学院本科招考试若干规定(2017年).PDF
- 中国高等教育学高等财经教育分会.PDF
- 中国(浙江)自由贸试验区总体方案.doc
- 中图分类号单位代号0280.doc
- 教科版(2017秋)科学二年级上册2.6 做一顶帽子 教学设计.docx
- 河北高频考点专训四 质量守恒定律的应用教学设计---2024-2025学年九年级化学人教版(2024)上册.docx
- 大单元教学【核心素养目标】6.3 24时计时法教学设计 人教版三年级下册.docx
- 河南省商城县李集中学2023-2024学年下学期九年级历史中考模拟八(讲评教学设计).docx
- 第18章 第25课时 正方形的性质2023-2024学年八年级下册数学课时分层作业教学设计( 人教版).docx
- Module 8 模块测试 教学设计 2024-2025学年英语外研版八年级上册.docx
- 2024-2025学年小学数学五年级下册浙教版教学设计合集.docx
- 2024-2025学年小学劳动四年级下册人民版《劳动》(2022)教学设计合集.docx
- 2024-2025学年小学数学三年级上册冀教版(2024)教学设计合集.docx
- 2024-2025学年高中生物学必修1《分子与细胞》人教版教学设计合集.docx
文档评论(0)