針對貪心法 I 提到三個例題裡，我們總是被題目要求要執行一連串的「任務」：
這讓我們能為所有的決策排出一個順序，使得我們能每次挑選最好的那項執行。
但有的時候這個所謂的「任務」可能不會寫在題目裡面，我們不妨來看看下面這道例題：
給你一個大於等於 $0$ 的整數 $N$，請你你找到最小的非負整數 $Q$ ，使得在 $Q$ 中所有位數（digit）的乘積等於 $N$。若找不到任何非負整數的位數乘積為 $N$，請輸出 $-1$。
例如：$N=10$，可以找到 $Q=25$，因為 $2\times 5=10$。
不曉得讀者對於上面這題是否有感受到問題了，那就是我們可能不知道從何開始「選擇」，畢竟我們沒有被指派所謂的「任務」。
遇到這種題目，我們必須要先一些簡單的觀察，首先搞清楚我們目標為何——找到最小、滿足條件的非負整數。
數字是如何比大小的呢？要注意到這裡不是簡單的用一個 < 運算子就好，因為題目關注的是數字的「位數」，所以我們可以想成當我們有兩個數字字串時，該如何去比較他們的大小：
因此，要找到最小的非負整數，我們的目標會是：
而這樣的觀察會引導出我們真正的任務為何：試圖不斷選擇最好的位數來乘出 $N$。此時便有個很單純的結論：不斷找到 $N$ 的因數中，$2\sim 9$ 內最大的那個，並將其放到數字的目前最高位。
會採取這樣的策略主要有以下幾個優勢：
如此一來我們就完成這題了。不過我們還是總結一下剛剛發生了什麼：
透過這道題目，希望能讓讀者感受到選擇並不總是題目給的，同時也期盼能給讀者一點「觀察性質」的啟發。
在貪心法的章節中，到目前為止我們似乎都只是很感性的去理解我們策略的正確性而已，不過如果比賽中我們「猜錯策略」導致浪費了時間撰寫這些錯誤解答的話，往往會造成不小的損失。
因此，在要寫解答之前，我們可以簡單的幫自己的演算法給出一點「證明」，來增加我們對策略的自信心、或是提早預防自己寫出錯誤的解答。我們不妨就拿先前解過的幾道例題來解釋。
讓我們來證明這題的策略正確性：
有 $N$ 塊蛋糕，經過你審慎評估後，你了解到對於第 $i$ 塊蛋糕他的好吃度為 $y_i$。但無奈的是由於你食量有限，你只能吃下 $K$ 塊蛋糕。
試問在最佳策略下，若要最大化吃下的蛋糕好吃度總和，這個總和最大可以是多少？
僅這題的策略看似很直接，但如果要稍微證明的話，還是可以講個一句話：因為我們獲得的好吃度是 $K$ 個數字的總和，既然我們都選了最大的 $K$ 個數字，那就不可能更好了。
像這樣直接找到「我們要最佳化的目標，有個顯然的上界」，往往能迅速的讓人接受策略的正確性。因為只要我們的策略能夠達到這個所謂的上界，那就沒有任何理由反駁他了。
讓我們來證明這題的策略正確性：
有 $N$ 份作業，你知道每一份作業你都只需要花一小時就能寫完，但可怕的是，第 $i$ 份作業再過 $d_i$ 小時就要截止了！
想要讓所有作業在截止前完成可能還有些困難，因此，你希望能完成越多份作業越好。試問在最佳策略下，你能有幾份作業在截止時間前寫完？
*註：若一份作業一小時後截止，你有辦法馬上開始寫這份作業來趕上死線
這題的策略是「每次選擇死線最早的作業做」，要如何證明這個策略的正確性呢？
不妨我們就假設「最佳策略不能先選擇死線最早的作業做」，這樣會如何呢？
對於這個「真正的最佳策略」，假設死線最早的作業是作業 $m$，若
既然我們改成先選擇死線最早的作業做都不會讓答案變差，這就造成了矛盾，因此，我們的假設是錯誤的，也就得到了我們策略的正確性。
像這樣透過「矛盾假設」的手法就稱為「反證法」，也是在證明貪心演算法時常見的一個手法。
讓我們來證明這題的策略正確性：
有 $N$ 位客人來吃飯，其中第一個人的餐點需要煮 $C_i$ 分鐘，且他需要花 $E_i$ 分鐘才能吃完他的餐點。你身為餐廳老闆，你知道你的廚房同一時間只能煮一道料理，但每位客人都可以互相不干涉的享用自己的餐點，而一道料理煮完後便能馬上讓對應的客人開始吃，也就是說，當你在第 $t$ 分鐘開始煮第 $i$ 位客人的餐點，那麼這道餐點會在第 $t+C_i$ 分鐘後煮好，且這位客人一定會在第 $t+C_i+E_i$ 分鐘後享用完畢。
試求在最佳的烹飪順序下，最後一個人享用完他的餐點時間最早可以多早？
這題的策略是「選擇吃最久的人點的餐點開始製作」，因此直接對用餐時間大到小排序就可以得到最佳順序，要如何證明這個策略的正確性呢？
這裡我們要使用的證明手法同樣是由反證法出發，但因為手法本身還多用到了一個巧思，因此才特別拿出來講。
首先，我們同樣假設「最佳順序不能經由用餐時間大到小排序」得出，因此，最佳順序肯定存在「相鄰的逆序數對」。
這時候，如果我們把 $i$ 和 $j$ 交換，會得到什麼呢？
我們不妨比較兩者造成的「用餐結束時間最大值」：
因次，透過上面的比較，我們就能發現交換相鄰逆序數對也不會讓答案變差，造成矛盾。
這類證明手法儘管比較不直覺，但卻能提供非常直接的正確性證據。
讓我們試著解決這題：
有一個長度為 $n$ 的書架，我們以序列 $a_1, a_2, \ldots, a_n$ 表示這個書架的狀態，$a_i=1$ 代表書架上有書，$a_i=0$ 則代表沒有。
現在你可以執行以下操作若干次：
請問你至少要執行幾次操作才能讓所有的書全部相鄰，也就是形成一個連續區間？
這題有一個很直接的貪心做法：每次選擇最左邊的連續一段書，將其全部往右一格。
但這樣直接移動可能會花費 $O(n^2)$ 的時間，雖然足以通過這題、要優化其實也不難，但有沒有更單純的做法呢？
可以觀察到，我們這樣的策略存在著一個直接的本質：每次移動，一定是在讓最左邊和最右邊兩本書中間的 $0$ 少一個。
反過來想，任何移動不也只能讓這個「中間的 $0$」的個數少一嗎？既然我們的策略能貼合這個「答案下限」，那我們的策略就是最佳的了。
因此，我們直接的證明了我們策略的最佳性──與此同時，我們還順便找到了一個超級好寫的作法：直接找到最左邊和最右邊的書，數中間有幾個 $0$ 就好！
這樣的做法不僅是 $O(n)$，還非常好寫。從這題我們也可以了解到，貪心策略有時候不一定要真的去實作，他可以僅僅是作為真的存在理想答案的「證據」，來讓我們直接計算答案後輸出。
讓我們來實際解決上次失敗的這題：
有 $N$ 個物品需要被堆在一個垂直的貨架上，已知第 $i$ 個物品的重量是 $w_i$，需要取用 $f_i$ 次，每次取用一個物品就需要將該物品上方的物品貨架升高才能做取用，因此取用一個物品消耗的能量為其上方的物品重量總和，而取用 $f_i$ 次就要花上 $f_i$ 倍的能量。
請問在最佳的物品擺放順序下，最小的能量消耗總和為何？
既然我們要幫所有物品排一個順序，不如大膽猜測：如果我們想要用逆序數對證明法證明我們的順序，會發生什麼事呢？
對於相鄰的兩個物品 $(i, j)$，交換他們與否同樣不會影響外側物品造成的花費，所以我們不妨專心比較交換這兩個物品的所造成的花費：
若要比較兩者的大小關係，可以發現：
既然我們確定了，每個物品都有唯一的數值可以拿來做比較，那事情就簡單了：直接對這個數字排序，照著模擬就行啦！所以我們便得到了一個 $O(N\log N)$ 的作法。
雖然我們在對分數做比較，但實際比大小的時候還是建議大家反著移項回去、使用交叉相乘的方式比大小，來避免浮點數可能產生的問題。
這類題目往往直覺上不好解決，但若透過倒推的方式，從證明手法開始思考的話，往往有時候可以神奇的把題目解決掉。
不過如果比賽要求快，真的需要這麼麻煩的去做假設、消項和移項嗎？這裡有幾個小技巧：
在卡加布列島上發行的硬幣有 $N$ 種，分別價值 $A_1, A_2, \cdots, A_N$ 塊，已知 $1 = A_1 < A_2 < \cdots < A_N$，而且對於所有可能的 $i$，$A_i$ 是 $A_{i+1}$ 的因數。學姐帶了價值 $K$ 塊錢的小說去卡加布列島想要換成現金，但她希望拿到的硬幣越少越好，作為收銀員的你能滿足學姐的需求嗎？
（注意到最小硬幣是 $1$ 塊錢，所以一定有辦法換錢）
卡加布列島上發行的硬幣有 $N$ 種，分別價值 $A_1, A_2, \cdots, A_N$ 塊，已知 $1 = A_1 < A_2 < \cdots < A_N$，而且對於所有可能的 $i$，$A_i$ 是 $A_{i+1}$ 的因數。
學姐這次帶了價值 $K$ 塊錢的遊戲王卡去卡加布列島想要換成現金，她一樣希望拿到的硬幣越少越好。作為收銀員的你，這次每個硬幣的數量都只有 $C_i$ 個可以給學姐換錢，不然你會被老闆罵。這次你能滿足學姐的需求嗎？
因為這裡的最小硬幣是 $1$ 塊錢而且你可以給學姐的 $1$ 塊錢有 $K$ 個，所以一定有辦法換錢，不用考慮無解的狀況。
給定一個長度為 $N$ 的字串 $s$，你可以執行下方一系列操作一次：
請問在執行一次操作後，得到的字串的最小字典序為何？
有 $n$ 場電影，第 $i$ 場電影的開始時間為 $a_i$、結束時間為 $b_i$。在不考慮移動時間的情況下，若你同一時間只能看一場電影，你最多可以看幾場電影？
小鴨工廠專門製造黃色小鴨，他們必須和塑膠原料廠訂購塑膠。一共有 $N$ 家塑膠原料廠，其中第 $i$ 家能從第 $s_i$ 天供貨到第 $t_i$ 天。
小鴨工廠想要選一些原料廠當合作對象。假設最早能供貨的原料廠開始時間是第 $S$ 天，能供貨到最晚的原料廠結束於第 $T$ 天，小鴨工廠希望從 $S$ 到 $T$ 的每天都要與一家原料廠合作。在此限制下，小鴨工廠希望合作廠商愈少愈好，請你回答至少需要幾家廠商。
住在月亮上山上的円円族，在舉行完祭月儀式後，並沒有順利解決問題，因為円円族長老所找到願意參加祭月儀式的円円數量實在是太少了。在那之後，由於月相的變異，導致了円円族主食高棕櫚的生產量越來越少，因此円円族們舉辦了部落會議來討論如何解決這個問題。
為了解決糧食問題，円円族決定要擴展他們的領土。円円族們原本居住在黃河流域（黃河又稱黃 River）北方的月亮山上，因為黃河曾經發展出黃河流域文化，円円族們看上了這一點打算要攻下黃河，佔地為王。經過部落會議之後，円円族們決定推派變態円円們去攻打黃 River。
居住在黃河流域的居民們得知這件事後，決定建造萬里長城來抵禦円円族的攻擊，請身為建築工程師的你幫忙。萬里長城的特色就是城牆一側總是一高一低的，居民們希望你造的城牆越長越好，而建造城牆的建材是石頭，每塊石頭可能有不同的高度。
但是供應石頭的廠商非常討厭，他每送一塊石頭就會問你要不要買，如果你不買，那塊就永遠不會再賣給你。而且時間非常緊迫，你一買一塊石頭就要馬上用，而且一定要按照購買的順序建造。
你透過一些內部的管道，得知廠商即將供應給你的石頭高度的順序，你能建造出多長的城牆呢？
有幾點可能要注意一下：
面試麵屋牡丹未果的赤井心，憤而在麵屋牡丹本店對面開了一家烏龍麵，想奪取麵屋牡丹的客源。為了具備和麵屋牡丹對抗的實力，赤井心開始認真研究烏龍麵的配方。她得知了一碗烏龍麵由以下兩個要素組成：麵團配方和調味料配方。
於是赤井心備齊了 $N$ 種麵團和 $N$ 種調味料，準備大展身手，搭配出 $N$ 碗烏龍麵。她發現每種麵團都與特定一種調味料會產生「絕配」。當第 $i$ 種麵團和某種調味料是絕配，會產生 $c_i$ 的美味程度；但也可能搭配特定一種調味料後會製造出地獄組合，損失 $d_i$ 點的美味程度。
如果某組麵團和調味料的搭配不是絕配，也不是地獄組合則美味程度為 $0$。浪費食材是不可饒恕的事，因此一種麵團一定跟洽一種調味料搭配，一種調味料也跟洽一種麵團搭配。
沒有學過演算法的赤井心來找你幫忙，她聽說你是個演算法高手。你能想辦法讓總美味程度最大嗎?
一臺圖靈機是擁有一個讀針和無限長的一張充滿格子的紙當作記憶體的機器。今天，你發現圖靈機掉落了 $N$ 張紙片，其中第 $i$ 張上面恰好寫滿了一個由小寫英文字母所組成的字串 $s_i$！你知道，圖靈機在壞掉之前想要做的事是：
舉例來說，假設你有三個字串 $[ab, abc, b]$，那如果排成 $[ab, b, abc]$ 的話，就會比 $[abc, b, ab]$ 還要小，因為前者拼起來是 abbabc 而後者拼起來是 abcbab。