一、簡介

① 貪心算法的基本概念

• 貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，它所做出的僅僅是在某種意義上的局部最優(yōu)解，它是最自然智慧的算法。
• 貪心算法用一種局部最功利的標準，總是能做出在當前看來是最好的選擇，難點在于證明局部最優(yōu)解最功利的標準可以得到全局最優(yōu)解。
• 貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。需要注意的是，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性（即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關）。因此，對所采用的貪心策略一定要仔細分析其是否滿足無后效性。

② 貪心算法的算法解釋

• 正例：通過一個例子來解釋，假設一個數(shù)組中 N 個正數(shù)，第一個挑選出來的數(shù)乘以 1，第二個挑選出來的數(shù)乘以 2，同理，第 N 次挑選出來的數(shù)乘以 N，總的加起來是我們的分數(shù)，那么怎么挑選數(shù)字使我們達到最大分數(shù)？
• 數(shù)組按從小到大的順序排序，按順序依次挑選，最終結(jié)果就是最大的。本質(zhì)思想是因子隨著挑選次數(shù)的增加會增大，盡量讓大數(shù)去結(jié)合大的因子。

③ 貪心算法的證明問題

• 如何證明貪心算法的有效性？一般來說，貪心算法不推薦證明，很多時候證明是非常復雜的。
• 例如：給定一個由字符串組成的數(shù)組 strs，必須把所有的字符串拼接起來，返回所有可能的拼接結(jié)果中，字典序最小的結(jié)果。<

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】之深入解析“贪心算法“的原理解析和算法实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。