4/4動態規劃經典案例詳解(背包問題)動態規劃經典案例詳解之背包問題

【

貪心準則3：價值密度pi/wi貪婪算法，這種選擇準則為：從剩余物品中選擇可裝入包的pi/wi值最大的物品，但是這種策略也不能保證得到最優解。利用此策略解n=3,w=[20,15,15],p=[40,25,25],c=30時的得到的就不是最優解。

由以上的三種貪心策略可知，本題如果采用貪心方法求解，則完全取決于輸入的數據，不管采用哪種方法都不能保證完全正確。

既然貪心不能解決，那么搜索行不行呢？我們可以深度搜索每種取物方案，然后依次對比得到的最終結果，取最大值即可。這個思路是正確的，結果也是可期的，但是時間代價是階乘級的，當物品數量很多（N>10就已經需要很長時間了）時，所耗費的時間代價是巨大的，對于奧賽要求一秒鐘內出解就根本不可能了，于是我們不得不想另外的思路，

【新思路】

要使物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1=wi),f[i-1,j]}

這樣，就可以自底向上地得出在前n件物品中取出若干件放進背包能獲得的最大價值，也就是f[n,c]

【算法偽代碼】

fori:=0tocdo{i=0也就是沒有物品時清零}

f[0,i]:=0;

fori:=1tondo{枚舉n件物品}

forj:=0tocdo{枚舉所有的裝入情況}

begin

f[i,j]:=f[i-1,j];{先讓本次裝入結果等于上次結果}

if(j>=w[i])and(f[i-1,j-w[i]]+p[i]>f[i,j]){如果能裝第i件物品}

thenf[i,j]:=f[i-1,j-w[i]]+p[i];{且裝入后價值變大則裝入}

end;

writeln(f[n,c]);

【輸入文件】

10

4

5143

40102530

【輸出結果】下面列出所有的f[i,j]

0000404040404040

10101010405050505050

10101025405050506575

10103040405055708080

分析次結果，可以很清楚的了解整個程序的執行過程，最后的80就是本題的答案。

【實例1：開心的金明（NOIP2006普及組真題）】

金明今天很開心，家里購置的新房就要領鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N元。于是，他把每件物品規定了一個重要度，分為5等：用整數1~5表示，第5等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j件物品的價格為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請你幫助金明設計一個滿足要求的購物單。

【輸入文件】

輸入的第1行，為兩個正整數，用一個空格隔開：

Nm（其中N（0，表示該物品為附件，q是所屬主件的編號）

【輸出格式】

輸出文件只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（<200000）。

【輸入樣例】

10005

80020

40051

30051

40030

50020

【輸出樣例】

2200

【分析】

本題跟上題非常類似，可以確認用背包問題可以解決，但是難度卻大大高于上題，這里提供兩個思路。

簡單方案：

對每一個物品做兩種決策，取與不取。如果取，滿足兩個條件：1.要么它是主件，要么它所屬的主件已經在包里了。2.放進去后的重要度與價格的成績的總和要比沒放進時的大。這兩個條件缺一不可的。于是得到如下的動規方程：

f[i,j]:=f[i-1,j];

if(i為主件ori的主件在包中）and(f[i,j]<f[i,j-v]+v*w)

thenf[i,j]:=f[i,j-v]+v*w;

這個方案看似簡單，其實有個非常復雜的問題，就是后一個條件“i的主件在包中”的判斷，因為動態規劃有個固有的弱點，就是很難知道整個中間過程，所以這個判斷其實寫起來是非常麻煩的。下面提供一個更好的方案：

改進方案：

細細的看題目，還一個很重要的條件我們還沒用：“每個主件可以有０個，１個或２個附件”。也就是說對于一套物品（包含主件，所有的附件），我們稱為一個屬類，對一個屬類的物品的購買方法，有以下５種：

１.一個都不買

２.主件

３.主件＋附件１

４.主件＋附件２

５.主件＋附件１＋附件２

這五種購買方法也是唯一的五種方法，也就是說對一屬類的物品，我們只有上述的５種購買方法。于是我們很自然的就會想到把物品按物品的屬類捆在一起考慮。這樣我們把物品

的屬類作為dp的狀態。可以得到如下的dp方程：

f[i,j]=max{f[i-1,j];第1種情況

f[i-1,j-v[i,0]]+v[i,0]*w[i,0];第2種情況

f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];第3種情況

f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2];第4種情況

f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}第5種情況這種方法的DP效率大大提高，不過需要對輸入數據進行重新處理，使之按屬類重新編號。

注意題目中還有一個條件：“每件物品都是10元的整數倍”，利用它就可以把速度在提高十倍。

【例題3積木城堡】

XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規則。

小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候并沒有預先考慮到這一點。所以他現在要改造城堡。由于他沒有多余的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最后的城堡都盡可能的高。

任務：請你幫助小XC編一個程序，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。

【輸入格式】

第一行是一個整數N(N<=100)，表示一共有幾座城堡。以下N行每行是一系列非負整數，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用-1結束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100。

【輸出格式】

一個整數，表示最后城堡的最大可能的高度。如果找不到合適的方案，則輸出0。

【輸入樣例】

2

21–1

321–1

【輸出樣例】

3

【分析】

本題初看也是可以用貪心法，但是跟之前的分析一樣，貪心法是無法保證完全正確的。但是本次的背包思路不像前兩個例子一樣清楚，我們可以先把所有積木城堡的高度全部計算出來，為了要讓所有城堡一樣高，那么這個高度肯定小于或等于最低城堡的高度（設為min），如果我們把這個高度當成一個背包的容量，然后對N個城堡求以min最高高度所需要的最多積木數，通