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

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

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

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

背包問題是算法設計中的經典問題。本文對不同的背包問題、解決背包問題的幾種常用算法設計技術及幾種不同貪心準則進行了介紹。并通過對不同貪心準則的討論，給出了一個解決連續背包問題最優解的貪心準則并用C語言程序得以實現。

連續背包問題；貪心算法；最優解

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

1.背包問題的分類

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

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

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

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

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

2.解決背包問題的常用算法設計技術

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

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

下面介紹常用的三種貪心準則：

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

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

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

3.用C語言實現貪心算法求解連續背包問題最優解

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

圖1 Main函數流程圖

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

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

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

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

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

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