1、一、裝箱問題（bin packing problem） 當(dāng)你裝一個(gè)箱子時(shí)，你會(huì)發(fā)現(xiàn)要使箱子盡可能裝滿不是一件很容易的事，你往往需要做些調(diào)整。從理論上講，裝箱問題是一個(gè)很難的組合優(yōu)化問題，即使用計(jì)算機(jī)也是不容易解決的。,1,裝箱問題是一個(gè)經(jīng)典的NP難解問題，這意味著該問題不存在在多項(xiàng)式時(shí)間內(nèi)求得精確解的算法（如果PNP）,因此對(duì)裝箱問題算法的研究指的是對(duì)其近似算法的研究，所謂近似算法即該算法可以求得與精確解接近的結(jié)果,但不一定得到精確解。,2,其在工業(yè)生產(chǎn)及日常生活中有廣泛的用途，其應(yīng)用在實(shí)際生活中無處不在，貨物裝運(yùn)，服裝裁剪，以及我們計(jì)算機(jī)科學(xué)中的存儲(chǔ)分配、共享資源調(diào)度、文件存儲(chǔ)都是裝箱問題在

2、實(shí)際應(yīng)用中的體現(xiàn)。所以具有重要的研究價(jià)值。,3,【問題】 裝箱問題問題描述：裝箱問題可簡述如下：設(shè)有編號(hào)為1、n的n種物品，體積分別為v1、v2、vn。將這n種物品裝到容量都為V的若干箱子里(更一般的裝箱問題還可以要求容量不是相同的)。約定這n種物品的體積均不超過V，即對(duì)于1i n，有0viV。不同的裝箱方案所需要的箱子數(shù)目可能不同。裝箱問題要求使裝盡這n種物品的箱子數(shù)要少。,4,裝箱問題的數(shù)學(xué)表示如下（ 0-1規(guī)劃模型）：,s.t.,yi =1表示箱子i裝入物品，反之表示箱子i空著,xij =1表示物品j裝入箱子i ，反之表示物品j未放入箱子i,5,若考察將n種物品的集合分劃成n個(gè)或小于n個(gè)

3、物品的所有子集，最優(yōu)解就可以找到。但所有可能劃分的總數(shù)太大。對(duì)適當(dāng)大的n，找出所有可能的劃分要花費(fèi)的時(shí)間是無法承受的。為此，對(duì)裝箱問題采用非常簡單的近似算法，即貪婪法。該算法依次將物品放到它第一個(gè)能放進(jìn)去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。,6,見lingo程序,例1 已知30個(gè)物品,其中6個(gè)長0.51m，6個(gè)長0.27m，6個(gè)長0.26m，余下12個(gè)長0.23m，箱子長為1m，問最少需多少個(gè)箱子才能把30個(gè)物品全部裝進(jìn)箱子。,裝箱問題的LINGO軟件求解,7,裝箱問題的近似求解算法,NF（Next Fit下次適應(yīng)）算法：按照物體給定的順序裝箱：把物品wi放到它第一個(gè)

4、能放進(jìn)去的箱子中。Bj是具有最大下標(biāo)的使用過的箱子，若wi的長度不大于Bj的剩余長度，則把wi放入Bj，否則把wi放入一個(gè)新的箱子Bj+1，且Bj在以后的裝箱中不再使用。 最后循環(huán),8,FF（First Fit首次適應(yīng) ）算法：按照物體給定的順序裝箱：把物品wi放到第一個(gè)箱子中。 B1 B2 Bj是當(dāng)前已經(jīng)使用過的箱子，在這些箱子中找一個(gè)長度不小于wi且下標(biāo)最小的箱子,將放入wi，如果不存在這樣的箱子,則另開一個(gè)新箱子Bj+1 , 將wi放入Bj+1中 。,9,在線算法：如果一個(gè)近似裝箱算法在執(zhí)行過程中，每當(dāng)一個(gè)物品到達(dá)時(shí)，就立刻決定把該物品放入哪個(gè)箱子中，而不管后序物品如何，這種算法就被稱為

5、在線算法。下次適應(yīng)算法、首次適應(yīng)算法等都是在線算法，其時(shí)間復(fù)雜度都為O(n) 。,以上算法都稱為在線適應(yīng)算法， 適應(yīng)算法的特點(diǎn)是當(dāng)處理當(dāng)前物品，如果有已經(jīng)打開的箱子中能夠放下這個(gè)物品，則不打開新的箱子。,10,不失一般性，對(duì)n件物品的體積按從大到小排好序，即有v1v2vn，然后按排序結(jié)果對(duì)物品重新編號(hào)即可。,降序首次適應(yīng)算法 （FFD）: 先將物體按長度從大到小排序,然后按FF算法對(duì)物體裝箱.,離線算法：如果算法在開始裝箱之前，已經(jīng)預(yù)先得到了所有物品的信息而一次性的確定裝箱策略，這種算法就被稱為離線算法。降序首次適應(yīng)算法和降序最佳適應(yīng)算法是兩個(gè)重要的離線算法。 這里的降序首次適應(yīng)算法就是一種貪

6、婪算法。,11,FFD算法： 輸入箱子的容積； 輸入物品種數(shù)n； 按體積從大到小順序，輸入各物品的體積； 預(yù)置已用箱子鏈為空； 預(yù)置已用箱子計(jì)數(shù)器box_count為0； for (i=0;in;i + ) 從已用的第一只箱子開始順序?qū)ふ夷芊湃胛锲穒 的箱子j； if （已用箱子都不能再放物品i） 另用一個(gè)箱子，并將物品i放入該箱子； box_count+； else 將物品i放入箱子j； ,12,裝箱問題中最早被研究的是一維裝箱問題。隨著研究的深入，人們發(fā)現(xiàn)實(shí)際生活中更多存在的是一些帶約束的裝箱問題，因此也就抽象化出了，如二維裝箱問題（條形裝箱問題、剪裁問題）、三維裝箱問題、變?nèi)菅b箱問題、有

7、色裝箱問題、對(duì)偶裝箱問題等等一系列的帶約束的裝箱問題。但是由于這些問題所與生俱來的復(fù)雜性，雖然已經(jīng)有一些研究成果發(fā)表了，但是其研究還是相當(dāng)?shù)睦щy。本文所討論的還是一維裝箱問題。,13,裝箱問題在工業(yè)生產(chǎn)及日常生活中有廣泛的用途，其應(yīng)用在實(shí)際生活中無處不在，如貨物裝運(yùn)，服裝裁剪，以及我們計(jì)算機(jī)科學(xué)中的存儲(chǔ)分配、共享資源調(diào)度、文件存儲(chǔ)都是裝箱問題在實(shí)際應(yīng)用中的體現(xiàn)。所以具有重要的研究價(jià)值。,14,例2: 多處理器調(diào)度問題 設(shè)有n個(gè)獨(dú)立的作業(yè)1,2,n，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的處理時(shí)間為ti。現(xiàn)約定，任何作業(yè)可以在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成

8、更小的子作業(yè)。 多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。 分析這個(gè)問題可以看成裝箱問題，也是NP完全問題。對(duì)于這一類問題，用貪婪選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。采用最長處理時(shí)間作業(yè)優(yōu)先的貪婪選擇策略可以設(shè)計(jì)出解多處理器調(diào)度問題的較好的近似算法。按此策略，當(dāng)nm時(shí)，我們只要將機(jī)器i的0,ti時(shí)間區(qū)間分配給作業(yè)i即可。 當(dāng)nm時(shí)，我們首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理器。,15,例如，設(shè)7個(gè)獨(dú)立作業(yè)1,2,3,4,5,6,7由3臺(tái)機(jī)器M1,M2,和M3來加工處理。各作業(yè)所需的處理時(shí)間分別為2

9、,14,4,16,6,5,3。按貪婪算法產(chǎn)生的作業(yè)調(diào)度如圖所示，所需的加工時(shí)間為17。,當(dāng)nm時(shí)，因此算法所需的計(jì)算時(shí)間復(fù)雜度為O(nlogn)。,16,例如,一個(gè)軟件開發(fā)小組要在規(guī)定時(shí)間內(nèi)完成一項(xiàng)任務(wù),系統(tǒng)分析員把任務(wù)劃分成各個(gè)子任務(wù).由于每個(gè)子任務(wù)要求的花費(fèi)程序員的時(shí)間不同,不合理的分派將導(dǎo)致各程序員貽誤工期. 這就是一個(gè)多處理器調(diào)度問題的應(yīng)用。,17,二、一維0/1背包問題 設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問選擇哪幾個(gè)物體裝入背包可以使其裝的最滿。 如直接用貪婪算法，將物體由大到小順次裝入背包，到裝不下時(shí)再逐個(gè)試裝更小

10、的一些，直至試到最小的一個(gè)或裝滿為止。按此處所給數(shù)據(jù)，先裝入54和45兩個(gè)，容積尚余11，最后只能再裝入體積為1的一個(gè)，總體積達(dá)到100，并不算太滿。此方法的好處是節(jié)省時(shí)間，主要的運(yùn)算時(shí)間是用來對(duì)n個(gè)元素進(jìn)行排序，故其復(fù)雜性是O（nlogn）。,18,如果對(duì)上述算法作一些改進(jìn)，可得到更好的結(jié)果。先從n個(gè)物體中試著取j個(gè)總體積不超過C的裝入背包，剩下的(n-j)個(gè)物體則利用貪婪算法盡量往里裝。此j值從零開始逐漸增加，反復(fù)進(jìn)行試探，直至j達(dá)到某預(yù)先給定的常數(shù)k(0kn)，最后從這些結(jié)果中取其最好的一個(gè)。如果在試探中能得到一個(gè)完全裝滿的方案，則此過程就可提前結(jié)束。因?yàn)閺膎個(gè)物體中取出j個(gè)共有 種方案

11、，此值隨著j的增加而增加較快，但可以證明此改進(jìn)算法的復(fù)雜性為O（knk+1）,因k是常數(shù)，故仍為多項(xiàng)式界的算法。,19,按本例所給數(shù)值，取j=0時(shí)，因就是前述普通貪婪算法，已經(jīng)得到100的結(jié)果；取j=1時(shí)，共有8種方案，當(dāng)用29或23先裝入時(shí)，可得到54+29+23+1=107的更好結(jié)果；取j=2時(shí)，共有28種方案，其中有能將背包完全裝滿的結(jié)果（43+23+29+14+1=110）。故知此問題當(dāng)取k2時(shí)就可得到最優(yōu)解。,20,當(dāng)n不太大時(shí)，適當(dāng)?shù)娜值，此改進(jìn)方法常常可以得到最優(yōu)解，但不能因此就說一般背包問題有多項(xiàng)式算法。當(dāng)n增大時(shí)，k不能隨著n不斷的加大，如k隨n增大而同時(shí)加大，其復(fù)雜性就是

12、指數(shù)型而不是多項(xiàng)式型的了，而如k取值較小，又不能保證得出最優(yōu)解。,21,求將哪些物品裝入背包可在滿足背包容量允許的前提下使價(jià)值總和最大。,背包問題也是經(jīng)典的NP-hard組合優(yōu)化問題之一,在經(jīng)濟(jì)管理、資源分配、投資決策、裝載設(shè)計(jì)等領(lǐng)域有著重要的應(yīng)用價(jià)值。,一維0/1背包問題的數(shù)學(xué)提法：,22,背包問題的數(shù)學(xué)模型描述如下：,23,問題自身的特性決定了該問題運(yùn)用貪婪算法可以得到最優(yōu)解或較優(yōu)解。通常這里有三種貪婪準(zhǔn)則:,1、價(jià)值貪婪準(zhǔn)則：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去，這種策略不能保

13、證得到最優(yōu)解。 2、質(zhì)量貪婪準(zhǔn)則：從剩下的物品中選擇可裝入背包的重量最小的物品，在一般情況下也不一定能得到最優(yōu)解。 3、價(jià)值密度貪婪準(zhǔn)則：從剩余物品中選擇可裝入包的cj /wj 值最大的物品，即按cj/wj 非遞增的次序裝入物品，只要正被考慮的物品裝得進(jìn)就裝入背包，這種策略可能會(huì)得到最優(yōu)解。,24,例：“超市大贏家”提供了50種商品作為獎(jiǎng)品供中獎(jiǎng)?lì)櫩瓦x擇,車的容量為1000dm3 , 獎(jiǎng)品i占用的空間為widm3 ,價(jià)值為vi 元, 具體的數(shù)據(jù)如下: vi = 220, 208, 198, 192, 180, 180, 165, 162, 160, 158,155, 130, 125, 122

14、, 120, 118, 115, 110, 105, 101, 100, 100, 98,96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58,56, 50, 30, 20, 15, 10, 8, 5, 3, 1 wi = 80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48,50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45,30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2,1。,25,(1)輸入物品個(gè)數(shù)n, 背包的容量l