周末開始着手算法這一系列文章,說起寫這一系列的初衷是發現網上很多的同學們在學習算法這個時候,會遇到很多困難,而學校書中講的道理盡管很對,但是總是太過于晦澀,正确的知識總是晦澀,這點沒錯,但讓晦澀的知識變得有趣豈不是也很有意思?回想起自己學習算法的過程中,遇到了不少的坑坑.特想寫一些文章去記錄下自己過程中的所思說想,也借這些文章自己複習學習一下.
這系列文章主要包括幾個大類的算法,包括貪心算法,分治法,動态規劃,回溯法,分支定界法,線性規劃法等等,具體在這些大類算法内每次會選幾個小例子去加深意識,并且會給出能夠運作的代碼來!這一點看起來很好笑,但是很重要,很多同學在看課本的時候都說算法書上的代碼都不能運作,太讨厭了,實際上書上是需要你了解算法而不是了解代碼.但是能夠運作的代碼同樣也有意義,能夠讓人迅速獲得喜悅和自信,當然了解也需要下一些苦功夫.
正文開始:
貪心算法其實本身就跟我們人性一樣,看到眼前的好吃的,拿來拿來别客氣.但是絲毫不顧忌自己還得燃燒卡路裡.貪心算法也是這樣.
貪心算法的本質其實就是總是做出目前最好的選擇,也就是說算法總是期望通過局部最優選擇進而得到全局最優的解決方案.
但是大家想想貪心算法其實是很”目光短淺”的,因為僅僅根據目前眼下的資訊來做出決策,這樣就不是從整體來最優考慮,他做出的選擇隻能是某種意義上的局部最優.但是,貪心算法可以得到很多問題的整體最優解或者近似解,在實際生活中還是有一定的意義的,是以貪心算法還是得到了廣泛的應用.
但是貪心也不是全部都要,貪心的算法也是有一定的原則,經過我們很多的實踐後發現,要想利用貪心算法解決問題,必須要滿足兩個性質:
1:貪心選擇
所謂的貪心選擇其實是說原問題可以分解成一個個的小問題來去求解,小問題的結果合成之後一樣是原問題的結果,這樣保證了每一步都是目前最佳的選擇,并且程式運作中沒有回溯過程.
2:最優子結構
最優子結構其實是說當一個問題的最優解包含其子問題的最優解時,稱此問題擁有最優子結構,問題能否擁有最優子結構其實是可否利用貪心算法的關鍵.
現在我們用一個例子說一下貪心算法:
現在我們有一批貨物,貨物的重量w和價值v都是不固定的,但是我們貨車的運載量是固定的,隻有m,但是貨物可以分割,是以怎麼樣可以讓運載的貨物價值最大呢?
現在我們有三種思路:
1:揀價值最高的貨物來運輸,肯定賺
2:揀重量最小的貨物來運輸,也不虧
3:選擇成本效益(價值/重量)大的貨物來運輸,看起來不錯
這三種方法想想也是第三種合理,第一種的盡管價值最大,但是如果貨物的重量也是非常大,這就不劃算了,如果選重量最小的貨物,如果賣不上價格,豈不也是很虧,是以,每次選擇成本效益最高的貨物,不失為一個優秀的選擇.
那讓我們設計一下算法:
1:資料結構及其初始化
我們這次使用結構體的方式,将n種貨物的重量,價值以及成本效益存儲在結構體當中,并且使用将其按照成本效益的高低來将其排序,
2:貪心政策
根據貪心政策,我們優先選擇成本效益高的貨物,并且每次放入後與運載能力m進行比較,求出最大值即可.
現在我們貼出代碼:
在代碼中輸入樣例:
運作結果如下:
下一篇文章我們将說說使用Dijkstra算法解決最短路徑問題,這也是貪心算法的一種,也是挺有意思的,還請多多指教.
參考資料:
1:大話資料結構,清華大學出版社
2:算法導論,機械工業出版社
3:趣學算法,人民郵電出版社
4:算法分析,人民郵電出版社