【摘 要】背包問題是算法設(shè)計(jì)中的經(jīng)典問題。本文對不同的背包問題、解決背包問題的幾種常用算法設(shè)計(jì)技術(shù)及幾種不同貪心準(zhǔn)則進(jìn)行了介紹。并通過對不同貪心準(zhǔn)則的討論，給出了一個(gè)解決連續(xù)背包問題最優(yōu)解的貪心準(zhǔn)則并用C語言程序得以實(shí)現(xiàn)。

【關(guān)鍵詞】連續(xù)背包問題；貪心算法；最優(yōu)解

背包問題是在1978年由Merkel和Hellman提出的。背包問題有很大的理論與應(yīng)用價(jià)值，在金融領(lǐng)域的投資決策、預(yù)算決策、項(xiàng)目選擇、資源分配和貨物裝載等方面均有重要的應(yīng)用。背包問題的實(shí)質(zhì)就是優(yōu)化的問題，即如何在有效的空間內(nèi)裝載更多的物品，實(shí)現(xiàn)背包價(jià)值的最大化。因此背包問題的最優(yōu)解問題已經(jīng)成為當(dāng)前研究的一大熱點(diǎn)和重點(diǎn)，它有助于提升應(yīng)用的水平，加快效率社會(huì)的建設(shè)步伐。本文主要通過對不同的背包、解決背包問題的幾種常用算法設(shè)計(jì)技術(shù)及幾種不同貪心準(zhǔn)則的討論，給出了一個(gè)解決連續(xù)背包問題最優(yōu)解的貪心準(zhǔn)則并用C語言程序得以實(shí)現(xiàn)。

1.背包問題的分類

現(xiàn)在我們討論的是用一維狀態(tài)實(shí)現(xiàn)背包問題，它可以分為以下幾類：

連續(xù)背包問題：有n件物品和一個(gè)載荷能力為m的背包。第i件物品的重量是，價(jià)值是。求解將哪些物品的部分裝入背包可使這些物品的總重量不超過背包容量，且價(jià)值總和最大。

0/1背包問題：有n件物品和一個(gè)載荷能力為m的背包。第i件物品的重量是，價(jià)值是。求解將哪些物品裝入背包可使這些物品的總重量不超過背包容量，且價(jià)值總和最大。它是最基礎(chǔ)的背包問題，包含了背包問題中設(shè)計(jì)狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成0/1背包問題求解。其特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。

多重背包問題：有n種物品和一個(gè)載荷能力為m的背包。第i種物品最多有q件可用，每件重量是，價(jià)值是。求解將哪些物品裝入背包可使這些物品的總重量不超過背包容量，且價(jià)值總和最大。將第i種物品分成若干件物品，其中每件物品有一個(gè)系數(shù)，這件物品的費(fèi)用和價(jià)值均是原來的費(fèi)用和價(jià)值乘以這個(gè)系數(shù)。使這些系數(shù)分別1，2，4，...，2^（k-1），q-2^k+1，且k是滿足n-2^k+1>0的最大整數(shù)。例如，如果q為13，就將這種物品分成系數(shù)分別為1，2，4，6的四件物品。分成的這幾件物品的系數(shù)和為q，表明不可能取多于q件的第i種物品。另外這種方法也能保證對于0..q間的每一個(gè)整數(shù)，均可以用若干個(gè)系數(shù)的和表示，這個(gè)證明可以分0..2^k-1和2^k..q兩段來分別討論得出。

完全背包問題：有n種物品和一個(gè)載荷能力為m的背包，每種物品都有無限件可用。第i種物品的的重量是，價(jià)值是。求解將哪些物品裝入背包可使這些物品的總重量不超過背包容量，且價(jià)值總和最大。

2.解決背包問題的常用算法設(shè)計(jì)技術(shù)

貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最優(yōu)的選擇，從而希望導(dǎo)致結(jié)果是最優(yōu)的算法。它是一種對某些求最優(yōu)解問題的更簡單、更迅速的設(shè)計(jì)技術(shù)。用貪心算法設(shè)計(jì)算法的特點(diǎn)是一步一步地進(jìn)行，常以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測度作最優(yōu)選擇，而不考慮各種可能的整體情況，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的。

貪心法有一個(gè)共同的點(diǎn)就是在最優(yōu)求解的過程中都采用一種局部最優(yōu)策略，把問題范圍和規(guī)模縮小，最后把每一步的結(jié)果合并起來得到一個(gè)全局最優(yōu)解。

下面介紹常用的三種貪心準(zhǔn)則：

價(jià)值貪心準(zhǔn)則：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品。如此繼續(xù)下去，這種策略不能保證得到最優(yōu)解。

重量貪心準(zhǔn)則：從剩下的物品中選擇可裝入背包的重量最小的物品。在一般情況下也不一定能得到最優(yōu)解。

價(jià)值密度/貪心準(zhǔn)則：從剩余物品中選擇可裝入包的/值最大的物品，即按/遞減的次序裝入物品，這種策略對于連續(xù)背包問題可保證得到最優(yōu)解。

3.用C語言實(shí)現(xiàn)貪心算法求解連續(xù)背包問題最優(yōu)解

連續(xù)背包問題的最優(yōu)貪心準(zhǔn)則是價(jià)值密度貪心準(zhǔn)則，其證明的基本思路是：把通過價(jià)值密度貪心準(zhǔn)則獲得的貪心解與任一可行解比較，若這兩個(gè)解不同，就開始尋找第一個(gè)不同的，然后設(shè)法用貪心解的去替換可行解的對應(yīng)分量，并證明可行解在分量替換后的總價(jià)值總是大于等于未替換前的值。反復(fù)進(jìn)行這種替換，直到新產(chǎn)生的可行解等于貪心解，即最優(yōu)解。若令x=[，……，]為用價(jià)值密度貪心準(zhǔn)則獲得的解，y=[，……，]為任意一個(gè)可行解，只需證明不失一般性，可以假設(shè)物品都按價(jià)值密度=/遞減排好了序，即（1in），然后分幾步用貪心解的去替換可行解的對應(yīng)分量，將轉(zhuǎn)化為，轉(zhuǎn)換過程中每一步都產(chǎn)生一個(gè)可行的新，且大于等于未轉(zhuǎn)化前的值，最后便可證明。以下圖1是利用C語言實(shí)現(xiàn)貪心算法求解連續(xù)背包問題最優(yōu)解的程序流程圖，圖2是其中的Pi/wi降序排列子程序流程圖。

下面考慮該領(lǐng)域常用的一個(gè)例子： n=7，m=15，p=[10，5，15，7，6，18，3]，w=[2，3，5，7，1，4，1]，程序分別對pi/wi價(jià)值密度、價(jià)值進(jìn)行降序排列，重量進(jìn)行升序排列，再應(yīng)用三種貪心算法進(jìn)行順序裝入，直到背包被裝滿。得到三種準(zhǔn)則的解并進(jìn)行比較得到最優(yōu)解。所得結(jié)果顯然可知價(jià)值密度貪心準(zhǔn)則為連續(xù)背包問題最優(yōu)解的貪心準(zhǔn)則。

參考文獻(xiàn)：

[1]M.H.Alsuwaiyel.算法設(shè)計(jì)技巧與分析[M].北京：電子工業(yè)出版社，2004.

[2]任瑞證，嚴(yán)蔚敏.整數(shù)背包問題的應(yīng)用及其算法研究[J].型微型計(jì)算機(jī)系統(tǒng)，2001，22（2）：204—206.

[3]游維.基于貪婪策略的0/1背包問題算法研究[J].計(jì)算機(jī)與現(xiàn)代化，2007，4：10-12，16.

作者簡介：

林宏（1976-），女，碩士，閩江學(xué)院物理學(xué)與電子信息工程系講師，研究方向：計(jì)算機(jī)軟件及算法。endprint