林 宏 / 閩江學(xué)院物理學(xué)與電子信息工程系

基于C語言的連續(xù)背包問題貪心算法研究

林 宏 / 閩江學(xué)院物理學(xué)與電子信息工程系

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

連續(xù)背包問題；貪心算法；最優(yōu)解

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

1.背包問題的分類

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

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

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

多重背包問題：有n種物品和一個載荷能力為m的背包。第i種物品最多有q件可用，每件重量是wi，價值是 pi。求解將哪些物品裝入背包可使這些物品的總重量不超過背包容量，且價值總和最大。將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(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間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0..2^k-1和2^k..q兩段來分別討論得出。

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

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

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

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

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

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

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

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

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

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

圖1 Main函數(shù)流程圖

圖2 Pi/wi降序排列子程序流程圖

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

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

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

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

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