一、基本思想
–>歸納、分析、選擇正確合適的貪心策略
在每一個區域階段，都做一個在當前“看上去”最優的決策，并期望通過每一次所做的區域最優選擇產生出一個全域最優解，做出貪心決策的依據稱為“貪心策略”，貪心策略一旦做出，就不可再更改，
二、3種證明方法（反證法，構造法，調整法）
1、反證法
用貪心的策略，依次構造出一個解 S1，假設最優解 S2 不同于S1，可以證明是矛盾的，從而得出 S1 就是最優解，（舉出反例）
eg：n個字串湊成最大整數
->將 A+B 與 B+A 相比較，如果前者大于后者，則認為 A>B，
2、構造法
根據描述的演算法，用貪心的策略依次構造出一個解，可證明一定是合法的解，即用貪心法找可行解，（舉例子）
eg：取火柴游戲（博弈論）
->轉成二進制后，進行異或，為0則先取必敗；為1則先取必勝
3、調整法
用貪心的策略，依次構造出一個解 S1，假設最優解 S2 不同于 S1，找出不同之處，在不破壞最優性的前提下，逐步調整 S2，最終使其變為 S1，從而 S1 也是最優解，（調整a[i]和a[j]進行比較）
eg：排隊接水
->把接水時間少的人盡可能排在前面
三、實時調整類貪心
–>每做一步決策都得重新調整決策
eg：桐桐的新聞系統
->將間隔從小到大排序，輸出一個（出隊）后將它加上間隔再入隊
四、貪心的常見模型
-
貨幣選擇問題
–>化異為同（先選面值大的，再選小的) -
區間調度問題
–>以結束時間遞增排序 -
部分背包問題
–>按照單位價值遞減排序 -
區間相關問題
(1)選擇不相交區間：
數軸上有 n 個開區間，選擇盡量多個區間，使得這些區間兩兩沒有公共點，
–>按照右端點遞增排序(2)區間選點問題：
數軸上有 n 個閉區間，取盡量少的點，使得每個區間內都至少有一個點，
–>按照右端點遞增排序&&左端點遞減排序(3)區間覆寫問題：
數軸上有 n 個閉區間，選擇盡量少的區間覆寫一條指定線段，
–>按照左端點遞增排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/287471.html
標籤：其他