貪心演算法入門——習題匯總-有解無憂

貪心演算法依賴于所做出的選擇無后效性，因此我們可以目光短淺，用區域最優解推出全域最優解，

貪心可能具有的優勢:降低時間復雜度，

一、背包相關問題

1.最優裝載問題

給出n個物體，第i個物體重量為wi，選擇盡量多的物體，使得總重量不超過C，

2.部分背包問題

有n個物體，第i個物體的重量為wi，價值為vi，在總重量不超過C的情況下讓總價值盡量高，

以vi/wi從大到小排序，
【深基12.例1】部分背包問題 - 洛谷https://www.luogu.com.cn/problem/P2240

3.乘船問題

有n個人，第i個人重量為wi，每艘船的最大載重量均為C，且最多只能乘兩個人，用最少的船裝載所有人，

先考慮最輕的人i，如果每個人都無法和他坐船，則只能每人乘一艘船，

否則，i應與能和他一起坐船的最重的j一起坐船，

[NOIP2007 普及組] 紀念品分組 - 洛谷https://www.luogu.com.cn/problem/P1094

二、區間問題

1.選擇不相交區間

數軸上有n個開區間（ai，bi），選擇盡可能多個區間，使得這些區間兩兩沒有公共點，

2.區間選點問題

數軸上有n個閉區間[ai，bi]，取盡量少的點，使得每個區間內都至少有一個點（不同區間內含的點可以是同一個），

3.區間覆寫問題

數軸上有n個閉區間[ai，bi]，選擇盡量少的區間覆寫一條指定線段[s,t]，

洛谷P1803凌亂的yyy凌亂的yyy / 線段覆寫 - 洛谷https://www.luogu.com.cn/problem/P1803

三、Huffman編碼問題

1.分卷子

有A,B,C,D四種等級的卷子，每次分卷子，只能將一摞卷子分為兩堆，不會有兩張相同等級的卷子同時出現在兩邊，分好的卷子還能繼續在分，直到分為四堆為止，給出各等級卷子的數量

[NOIP2004 提高組] 合并果子 / [USACO06NOV] Fence Repair G - 洛谷https://www.luogu.com.cn/problem/P1090

四、貪心+公式

1.排隊接水 - 洛谷貪心+快排

2.[NOIP2012 提高組] 國王游戲 - 洛谷貪心+高精度

3.122. 買賣股票的最佳時機 II - 力扣（LeetCode） (leetcode-cn.com)

五、貪心+模擬

1.擺動序列

376. 擺動序列 - 力扣（LeetCode） (leetcode-cn.com)

2.最大子序和

53. 最大子序和 - 力扣（LeetCode） (leetcode-cn.com)

3.55. 跳躍游戲 - 力扣（LeetCode） (leetcode-cn.com)

4.1005. K 次取反后最大化的陣列和 - 力扣（LeetCode） (leetcode-cn.com)

****5.135. 分發糖果 - 力扣（LeetCode） (leetcode-cn.com)

455. 分發餅干 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/assign-cookies/

六、貪心的其他應用

字典序問題（偷懶不想講）

最小生成樹、單源最短路徑的Dijkstra演算法、集合覆寫問題的Chvátal演算法，

我不會，嫑問我，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/356844.html

標籤：其他