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

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

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

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

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

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

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

1.背包問(wèn)題的分類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖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]，程序分別對(duì) pi/wi價(jià)值密度、價(jià)值進(jìn)行降序排列,重量進(jìn)行升序排列，再應(yīng)用三種貪心算法進(jìn)行順序裝入，直到背包被裝滿。得到三種準(zhǔn)則的解并進(jìn)行比較得到最優(yōu)解。所得結(jié)果顯然可知價(jià)值密度貪心準(zhǔn)則為連續(xù)背包問(wèn)題最優(yōu)解的貪心準(zhǔn)則。

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

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

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

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