聽起來高大上的“算法”，其實一點也不難！
專欄《最簡單易懂的10堂算法入門課》用最簡潔的語言和邏輯，脫離編程語言的束縛，在最短時間內，從算法概念/程序結構/數據結構/算法思想/應用方法這五個方面，跟您一起，輕鬆地理解算法知識，掌握算法思維。
小複習
- 程序結構有哪些？
順序/循環/分支。
- 數據結構有哪些？
低階的有：數組/鏈表/堆棧/隊列
高階的有：樹/集/映射/圖
算法思想
算法思想就是解題思路，是算法程序的提綱，常見的算法思想就4種：
貪心算法（Greedy Algorithm）
分治算法（Divide and Conquer）
動態規劃（Dynamic Programming）
窮舉搜索（Exhaustive Searching）
可以說90%以上的算法，都來自這4種基本思想，掌握它們，再設計算法時，就“才思泉湧，下筆有神”了。
貪心算法
貪心算法，聽著不怎麼熟悉，其實是最最常用常見的算法了，因為它的思想太樸素了——
一個問題有點難，一時找不到最優解，那麼就把原問題拆成幾個小問題，分別求每個小問題的最優解，再把這些“局部最優解”疊起來，就“算是”整體最優解了。
通過我上面的描述，也可以猜出一個結論——
貪心算法得到最終結果，很有可能並不是全局最優解，但是可能會比較接近最優解。
在每一步中，選擇目前最優的策略而並不考慮長遠，這種短視被叫做——
貪心！
貪心——只看到局部最優解
再合理不過了，對吧？
三步完成貪心算法
- 第一步
定義什麼是最優解
- 第二步
定義什麼是子問題的最優解
- 第三步
分別求出子問題的最優解再堆疊出全局最優解
就是這麼簡單！
上個例子加強理解——0-1揹包問題
0-1揹包問題是一種非常常見且典型的問題，問題的模式的是這樣：
有一個揹包，最多能承載150斤的重量，現在有7個物品，重量分別為[35, 30, 60, 50, 40, 10, 25]，它們的價值分別為[10, 40, 30, 50, 35, 40, 30]，現在想要用這個揹包揹走最多價值的物品，怎麼背？
0-1揹包問題
其實這類問題再常見不過了，對於選擇的物品有一個總和限制，比如這裡的重量，又希望另一個屬性的總和最大，比如這裡的價值。
每一個物品，要麼選擇（1），要麼放棄（0），這就是0-1揹包問題。
實操一下吧
還是分三步：
- 第一步
定義什麼是最優解
這裡很明顯，在重量限制範圍內，價值最大的選擇，就是最優解。
- 第二步
定義什麼是子問題的最優解
子問題定義為每一次拿什麼物品，那麼子問題的最優解怎麼定義？
其實有很多定義方法，這裡選擇一種最直接的方式——
認為每次都儘量選擇當前價值最高的物品，這就是“局部最優解”。
- 第三步
分別求出子問題的最優解再堆疊出全局最優解
按照制訂的規則來選一下吧，順序是：4 2 6 5 。
最終的總重量是：130。
最終的總價值是：165。
子問題最優解還有不同的定義方法
子問題的最優解有各種定義方法，這些方法決定了最終的結果究竟有多接近真正的全局最優解。
比如上面的0-1揹包問題，還可以這樣定義：
認為每次都選擇當前物品中重量最小的，策略是： 6 7 2 1 5。
可以看出這樣比上面能夠多放入一樣物品，總重量是140，但是總價值是155卻並沒有上面方法更優。
還可以這樣定義：
認為每次要選擇“價值密度”最高的物品，（價值密度是指單位重量的價值），順序是：6 2 7 4 1， 總重量是150，總價值是170。
可以看出最後一種定義方法最優，那麼是不是以後0-1揹包問題都這樣去定義子問題呢？
其實未必。
一種定義方式往往可能只在一種特定條件下是最優，新條件下可能最不是最優了。
用貪心算法三個核心問題：
1 為什麼不直接求全局最優解？
這是使用貪心算法的前提，即出現這幾種情況：
原問題複雜度過高；
求全局最優解的數學模型難以建立；
求全局最優解的計算量過大；
沒有太大必要一定要求出全局最優解，“比較優”就可以。
那麼幾乎99%就要使用貪心算法的思想來解決問題。
2 怎樣把原問題分解成子問題？
一般根據問題的邏輯解構有這麼幾種分法：
- 按串行任務分
時間串行的任務，按子任務來分解，即每一步都是在前一步的基礎上再選擇當前的最優解。
- 按規模遞減分
規模較大的複雜問題，可以藉助遞歸思想（見第2課），分解成一個規模小一點點的問題，循環解決，當最後一步的求解完成後就得到了所謂的“全局最優解”。
- 按並行任務分
這種問題的任務不分先後，可能是並行的，可以分別求解後，再按一定的規則（比如某種配比公式）將其組合後得到最終解。
3 如何知道貪心法的結果逼近了真正的最優解
依靠邏輯分析，依靠以往經驗，“感覺”比較使用這種方法誤差不會超出忍受範圍了，就可以。
算法無“最優”
學完這一講，我們應該對算法設計有這麼一個新印象了——
它跟純數學不同，並不追求絕對的最優解，因為追求的過程需要考慮：
- 成本
耗費多少資源，花掉多少編程時間。
- 速度
計算量是否過大，計算速度能否滿足要求。
- 價值
得到了最優解與次優解是否真的有那麼大的差別，還是說差別可以忽略。
理解了貪心算法，幾乎就等同理解了大部分的算法設計者是怎麼思考問題的。