晏 杰

（武夷學(xué)院，福建 武夷山 354300）

Matlab中貪婪算法求解背包問(wèn)題的研究與應(yīng)用

晏 杰

（武夷學(xué)院，福建 武夷山 354300）

本文對(duì)貪婪算法進(jìn)行了分析，總結(jié)了貪婪算法解決問(wèn)題的思路，根據(jù)改進(jìn)的貪婪算法解決策略，通過(guò)Matlab對(duì)貪婪算法在背包問(wèn)題中的應(yīng)用進(jìn)行了具體實(shí)現(xiàn)和詳細(xì)的分析.

Matlab；貪婪算法；背包；研究與應(yīng)用

1 引言

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

2 貪婪算法概述

2.1 貪婪算法的定義

貪婪算法又叫登山法，它的根本思想是逐步到達(dá)山頂，即逐步獲得最優(yōu)解，是解決最優(yōu)化問(wèn)題時(shí)的一種簡(jiǎn)單但適用范圍有限的策略.

2.2 貪婪算法思想

貪婪算法采用逐步構(gòu)造最優(yōu)解的方法，即在每個(gè)階段，都選擇一個(gè)看上去最優(yōu)的策略（在一定的標(biāo)準(zhǔn)下）.策略一旦選擇就不可再更改，貪婪決策的依據(jù)稱為貪婪準(zhǔn)則，也就是從問(wèn)題的某一個(gè)初始解出發(fā)并逐步逼近給定的目標(biāo)，以盡可能快的要求得到更好的解.而且它在設(shè)計(jì)時(shí)沒(méi)有固定的框架，關(guān)鍵在于貪婪策略的選擇.但要注意的是選擇的貪婪策略要具有無(wú)后向性，即某階段狀態(tài)一旦確定下來(lái)后，不受這個(gè)狀態(tài)以后的決策的影響，也就是說(shuō)某狀態(tài)以后的過(guò)程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān).

2.3 貪婪算法的特性

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

（1）有一個(gè)以最優(yōu)方式來(lái)解決的問(wèn)題.為了構(gòu)造問(wèn)題的解決方案,有一個(gè)候選的對(duì)象的集合.

（2）隨著算法的進(jìn)行,將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過(guò)并被選出的候選對(duì)象,另一個(gè)包含已經(jīng)被考慮過(guò)但被丟棄的候選對(duì)象.

（3）有一個(gè)函數(shù)來(lái)檢查一個(gè)候選對(duì)象的集合是否提供了問(wèn)題的解答.該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu).

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

（5）選擇函數(shù)可以指出哪一個(gè)剩余的候選對(duì)象最有希望構(gòu)成問(wèn)題的解.

（6）最后,目標(biāo)函數(shù)給出解的值.

2.4 貪婪算法解決問(wèn)題的步驟

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

（1）明確問(wèn)題的求解目標(biāo).

（2）分析問(wèn)題所包含的約束條件.

（3）建立優(yōu)化函數(shù).

（4）制定貪婪準(zhǔn)則.

清楚問(wèn)題的求解目標(biāo)、所包含的約束條件及優(yōu)化函數(shù)之后，就可以著手制定一個(gè)可行的貪婪準(zhǔn)則.貪婪準(zhǔn)則的制定是用貪婪算法解決最優(yōu)化問(wèn)題的關(guān)鍵，它關(guān)系到問(wèn)題能否得到成功解決及解決質(zhì)量的高低.

3 Matlab中貪婪算法求解背包問(wèn)題的具體實(shí)現(xiàn)

3.1 問(wèn)題描述

有一組物品共有9種，給出每種物品的重量、價(jià)值、單位價(jià)值.假設(shè)背包總?cè)萘繛?0千克，請(qǐng)確定裝包方案，要求所裝物品總重量不超過(guò)30千克且總價(jià)值最大.具體數(shù)據(jù)如下表所示：

物品號(hào) 重量（千克） 價(jià)值（元） 單位價(jià)值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中貪婪算法求解背包問(wèn)題的關(guān)鍵代碼

%per_value已經(jīng)按降序排好，其他參數(shù)也對(duì)應(yīng)排好.

3.3 求解過(guò)程

先建立greedy_beibao函數(shù)的4個(gè)參數(shù)，具體如下：

然后調(diào)用greedy_beibao函數(shù)進(jìn)行求解，并得到最終結(jié)果.

3.4 運(yùn)行結(jié)果

輸出對(duì)應(yīng)裝入背包的物品號(hào)chanpin_N=928 473501.

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

3.5 結(jié)果分析

通過(guò)程序運(yùn)行的結(jié)果，我們可以看出，9種物品中除了物品6以外的8種物品都裝入了背包,這時(shí)總價(jià)值最大為1015元,對(duì)應(yīng)背包重量為28.5千克，裝入背包的物品編號(hào)依次為：9284735 1.

4 結(jié)束語(yǔ)

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

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

〔2〕劉洋.0-1 背包的遺傳算法及其改進(jìn)[J].天津師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2003.

〔3〕肖小文.設(shè)施區(qū)位決策支持系統(tǒng)設(shè)計(jì)與開(kāi)發(fā)[M].華東師范大學(xué)出版社，2010.

TP18

A

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