Matlab中貪婪算法求解背包問題的研究與應用

晏 杰

（武夷學院，福建 武夷山 354300）

Matlab中貪婪算法求解背包問題的研究與應用

晏 杰

（武夷學院，福建 武夷山 354300）

本文對貪婪算法進行了分析，總結了貪婪算法解決問題的思路，根據改進的貪婪算法解決策略，通過Matlab對貪婪算法在背包問題中的應用進行了具體實現和詳細的分析.

Matlab；貪婪算法；背包；研究與應用

1 引言

為了滿足人們對大數據量信息處理的渴望,為解決各種實際問題,計算機算法學得到了飛速的發展,線性規劃、動態規劃、貪婪策略等一系列運籌學模型紛紛運用到計算機算法學中,產生了解決各種現實問題的有效算法.貪婪算法主要用于設計數值最優化問題的算法，它是一種求最優解問題的最直接的設計技術，它不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題能產生整體最優解或者整體最優解的近似解.算法容易實現也易于理解，這使得算法在編碼和執行的過程中都有著一定的速度優勢，同時也提高了效率并節省了時間.

2 貪婪算法概述

2.1 貪婪算法的定義

貪婪算法又叫登山法，它的根本思想是逐步到達山頂，即逐步獲得最優解，是解決最優化問題時的一種簡單但適用范圍有限的策略.

2.2 貪婪算法思想

貪婪算法采用逐步構造最優解的方法，即在每個階段，都選擇一個看上去最優的策略（在一定的標準下）.策略一旦選擇就不可再更改，貪婪決策的依據稱為貪婪準則，也就是從問題的某一個初始解出發并逐步逼近給定的目標，以盡可能快的要求得到更好的解.而且它在設計時沒有固定的框架，關鍵在于貪婪策略的選擇.但要注意的是選擇的貪婪策略要具有無后向性，即某階段狀態一旦確定下來后，不受這個狀態以后的決策的影響，也就是說某狀態以后的過程不會影響以前的狀態，只與當前狀態有關.

2.3 貪婪算法的特性

貪婪算法及貪婪算法可解決的問題通常大部分都有如下的特性:

（1）有一個以最優方式來解決的問題.為了構造問題的解決方案,有一個候選的對象的集合.

（2）隨著算法的進行,將積累起其它兩個集合：一個包含已經被考慮過并被選出的候選對象,另一個包含已經被考慮過但被丟棄的候選對象.

（3）有一個函數來檢查一個候選對象的集合是否提供了問題的解答.該函數不考慮此時的解決方法是否最優.

（4）還有一個函數檢查是否一個候選對象的集合是可行的,也即是否可能往該集合上添加更多的候選對象以獲得一個解.和上一個函數一樣,此時不考慮解決方法的最優性.

（5）選擇函數可以指出哪一個剩余的候選對象最有希望構成問題的解.

（6）最后,目標函數給出解的值.

2.4 貪婪算法解決問題的步驟

使用貪婪算法解決問題，通常需要做好以下幾個方面的工作：

（1）明確問題的求解目標.

（2）分析問題所包含的約束條件.

（3）建立優化函數.

（4）制定貪婪準則.

清楚問題的求解目標、所包含的約束條件及優化函數之后，就可以著手制定一個可行的貪婪準則.貪婪準則的制定是用貪婪算法解決最優化問題的關鍵，它關系到問題能否得到成功解決及解決質量的高低.

3 Matlab中貪婪算法求解背包問題的具體實現

3.1 問題描述

有一組物品共有9種，給出每種物品的重量、價值、單位價值.假設背包總容量為30千克，請確定裝包方案，要求所裝物品總重量不超過30千克且總價值最大.具體數據如下表所示：

物品號 重量（千克） 價值（元） 單位價值9 3 300 100 2 45 45 8 4 180 45 1 4 2.5 100 40 7 5 200 40 3 30 30 5 10 150 15 6 6 90 15 1 1 2 10 5

3.2 Matlab中貪婪算法求解背包問題的關鍵代碼

%per_value已經按降序排好，其他參數也對應排好.

3.3 求解過程

先建立greedy_beibao函數的4個參數，具體如下：

然后調用greedy_beibao函數進行求解，并得到最終結果.

3.4 運行結果

輸出對應裝入背包的物品號chanpin_N=928 473501.

輸出裝入物品后背包總重量ans=28.5000.輸出裝入物品后背包總價值ans=1015.

3.5 結果分析

通過程序運行的結果，我們可以看出，9種物品中除了物品6以外的8種物品都裝入了背包,這時總價值最大為1015元,對應背包重量為28.5千克，裝入背包的物品編號依次為：9284735 1.

4 結束語

貪婪算法的優點在于在求解問題的每一步它都是選擇最優解，算法就容易實現也易于理解，這使得算法在編碼和執行的過程中都有著一定的速度優勢，同時也提高了效率并節省了時間.然而貪婪算法的缺點也是不容忽視的，由于它采取逐步獲得最優解的方法而不從整體最優上加以考慮，它所做出的僅是在某種意義上的局部最優解.因此貪婪算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它都能得出整體最優解或者是整體最優解的近似解.與回溯法等比較,它的適用區域相對狹窄許多,因此正確地判斷它的應用時機十分重要，不過貪婪算法的優點結合其他算法的應用將是以后研究的方向.

〔1〕王德才.基于能量分析的地震動輸入選擇及能量譜研究[M].合肥工業大學出版社，2010.

〔2〕劉洋.0-1 背包的遺傳算法及其改進[J].天津師范大學學報（自然科學版），2003.

〔3〕肖小文.設施區位決策支持系統設計與開發[M].華東師范大學出版社，2010.

TP18

A

1673-260X（2012）09-0023-02