標籤:pascal典型問題

背包問題(Knapsack problem)是一種組合優化的NP完全問題。問題可以描述為:給定一組物品,每種物品都有自己的重量和價格,在限定的總重量內,我們如何選擇,才能使得物品的總價格最高。問題的名稱來源於如何選擇最合適的物品放置於給定背包中。相似問題經常出現在商業、組合數學,計算複雜性理論、密碼學和應用數學等領域中。也可以將背包問題描述為決定性問題,即在總重量不超過W的前提下,總價值是否能達到V?它是在1978年由Merkel和Hellman提出的。

1簡介

它的主要思路是假定某人擁有大量物品,重量各不同。此人通過秘密地選擇一部分物品並將它們放到背包中
背包問題
來加密消息。背包中的物品總重量是公開的,所有可能的物品也是公開的,但背包中的物品是保密的。附加一定的限制條件,給出重量,而要列出可能的物品,在計算上是不可實現的。背包問題是熟知的不可計算問題,背包體制以其加密,解密速度快而引人注目。但是,大多數一次背包體制均被破譯了,因此很少有人使用它。

2背包問題

基本思路
這是最基礎的背包問題,特點是:每種物品僅有一件,可以選擇放或不放。
用子問題定義狀態:即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。可以壓縮空間,f[v]=max{f[v],f[v-c[i]]+w[i]}
這個方程非常重要,基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下:「將前i件物品放入容量為v的背包中」這個子問題,若只考慮第i件物品的策略(放或不放),那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品,那麼問題就轉化為「前i-1件物品放入容量為v的背包中」,價值為f[i-1][v];如果放第i件物品,那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」,此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
注意f[v]有意義當且僅當存在一個前i件物品的子集,其費用總和為v。所以按照這個方程遞推完畢后,最終的答案並不一定是f[N] [V],而是f[N][0..V]的最大值。如果將狀態的定義中的「恰」字去掉,在轉移方程中就要再加入一項f[v-1],這樣就可以保證f[N] [V]就是最後的答案。至於為什麼這樣就可以,由你自己來體會了。
示常式序
// BY 劉摶羽
#include "stdafx.h"
#include <iostream>
using namespace std;
#define MAXSIZE 1000
int f[MAXSIZE + 1],c[MAXSIZE + 1],w[MAXSIZE + 1];
int _tmain(int argc,_TCHAR* argv[])
{
int N,V;
cin >> N >> V;
int i = 1;
for (; i <= N; ++i)
{
cin >> c[i] >> w[i];
}
for (i = 1; i <= N; ++i)
{
for (int v = V; v >= c[i]; --v) //c[i]可優化為bound,bound = max {V - sum c[i,...n],c[i]}
{
f[v] = (f[v] > f[v - c[i]] + w[i]?f[v] : f[v - c[i]] + w[i]);
}
}
//當i=N時,可以跳出循環單獨計算F[V]
cout << f[V] << '\n';
system("pause");
return 0;
}
程序
程序一:
var
i,j,v,n:longint;
f,c,w:array[0..100]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
read(n,v);
fillchar(f,sizeof(f),0);
for i:=1 to n do
read(c[i],w[i]);
for i:=1 to n do
for j:=v downto c[i] do
f[j]:=max(f[j],f[j-c[i]]+w[i]);
writeln(f[v]);
end.
程序二(順推法):
var m,n,x,i:integer;
c,w:array[1..30]of integer;
f:array[0..30,0..300]of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(n,m);
for i:=1 to n do
readln(c[i],w[i]);
for i:=1 to n do
for x:=1 to m do
if x>=c[i] then f[i,x]:=max(f[i-1,x-c[i]]+w[i],f[i-1,x])
else f[i,x]:=f[i-1,x];
writeln(f[n,m]);
end.
總結
0/1背包問題是最基本的背包問題,它包含了背包問題中設計狀態、方程的最基本思想,另外,別的類型的背包問題往往也可以轉換成0/1背包問題求解。故一定要仔細體會上面基本思路的得出方法,狀態轉移方程的意義,以及最後怎樣優化的空間複雜度。

3完全背包

基本思路
這個問題非常類似於01背包問題,所不同的是每種物品有無限件。也就是從每種物品的角度考慮,與它相關的策略已並非取或不取兩種,而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路,令f[i,v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的策略寫出狀態轉移方程,像這樣:f[i,v]=max{f[i,v-vi]+wi,f[i-1,v]}。這跟01背包問題一樣有O(N*V)個狀態需要求解,但求解每個狀態的時間則不是常數了,求解狀態f[v]的時間是O(v/c),總的複雜度是超過O(VN)的。
將01背包問題的基本思路加以改進,得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要,可以推及其它類型的背包問題。但我們還是試圖改進這個複雜度。
轉為問題
既然01背包問題是最基本的背包問題,那麼我們可以考慮把完全背包問題轉化為01背包問題來解。最簡單的想法是,考慮到第i種物品最多選V/c 件,於是可以把第i種物品轉化為V/c件體積及價值均不變的物品,然後求解這個01背包問題。這樣完全沒有改進基本思路的時間複雜度,但這畢竟給了我們將完全背包問題轉化為01背包問題的思路:將一種物品拆成多件物品。
更高效的轉化方法是:把第i種物品拆成體積為c*2^k、價值為w*2^k的若干件物品,其中k滿足c*2^k<V。這是二進位的思想,因為不管最優策略選幾件第i種物品,總可以表示成若干個2^k件物品的和。這樣把每種物品拆成O(log(V/c))件物品,是一個很大的改進。但我們有更優的O(VN)的演算法。* O(VN)的演算法 這個演算法使用一維數組,先看偽代碼:<pre class"example"> for i=1..N for v=0..V f[v]=max{f[v],f[v-c]+w};
你會發現,這個偽代碼與P01的偽代碼只有v的循環次序不同而已。為什麼這樣一改就可行呢?首先想想為什麼P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[v]是由狀態f[v-c]遞推而來。換句話說,這正是為了保證每件物品只選一次,保證在考慮「選入第i件物品」這件策略時,依據的是一個絕無已經選入第i件物品的子結果f[v-c]。而完全背包的特點恰是每種物品可選無限件,所以在考慮「加選一件第i種物品」這種策略時,卻正需要一個可能已選入第i種物品的子結果f[v-c],所以就可以並且必須採用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。
這個演算法也可以以另外的思路得出。例如,基本思路中的狀態轉移方程可以等價地變形成這種形式:f[v]=max{f[v],f[v-c]+w},將這個方程用一維數組實現,便得到了上面的偽代碼。
總結
完全背包問題也是一個相當基礎的背包問題,它有兩個狀態轉移方程,分別在「基本思路」以及「O(VN)的演算法「的小節中給出。希望你能夠對這兩個狀態轉移方程都仔細地體會,不僅記住,也要弄明白它們是怎麼得出來的,最好能夠自己想一種得到這些方程的方法。事實上,對每一道動態規劃題目都思考其方程的意義以及如何得來,是加深對動態規劃的理解、提高動態規劃功力的好方法。

4多重問題

基本演算法
這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可,因為對於第i種物品有n+1種策略:取0件,取1件……取 n件。令f[v]表示前i種物品恰放入一個容量為v的背包的最大權值,則:f[v]=max{f[v-k*c]+ k*w|0<=k<=n}。複雜度是O(V*∑n)。
演算法
多重背包問題同樣有O(VN)的演算法。這個演算法基於基本演算法的狀態轉移方程,但應用單調隊列的方法使每個狀態的值可以以均攤O⑴的時間求解。由於用單調隊列優化的DP已超出了NOIP的範圍,故本文不再展開講解。我最初了解到這個方法是在樓天成的「男人八題」幻燈片上。
問題
如果將P01、P02、P03混合起來。也就是說,有的物品只可以取一次(01背包),有的物品可以取無限次(完全背包),有的物品可以取的次數有一個上限(多重背包)。應該怎麼求解呢?
小結
有人說,困難的題目都是由簡單的題目疊加而來的。這句話是否公理暫且存之不論,但它在本講中已經得到了充分的體現。本來01背包、完全背包、多重背包都不是什麼難題,但將它們簡單地組合起來以後就得到了這樣一道一定能嚇倒不少人的題目。但只要基礎紮實,領會三種基本背包問題的思想,就可以做到把困難的題目拆分成簡單的題目來解決。

5二維費用

演算法
費用加了一維,只需狀態也加一維即可。設f[v]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。狀態轉移方程就是:fi[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}。如前述方法,可以只使用二維的數組:當每件物品只可以取一次時變數v和u採用逆序的循環,當物品有如完全背包問題時採用順序的循環。當物品有如多重背包問題時拆分物品。
小結
事實上,當發現由熟悉的動態規劃題目變形得來的題目時,在原來的狀態中加一維以滿足新的限制是一種比較通用的方法。希望你能從本講中初步體會到這種方法。

6分組背包

演算法
這個問題變成了每組物品有若干種策略:是選擇本組的某一件,還是一件都不選。也就是說設f[k][v]表示前k組物品花費費用v能取得的最大權值,則有f[k][v]=max{f[k-1][v],f[k-1][v-c]+w|物品i屬於第k組}。
使用一維數組的偽代碼如下:
for 所有的組k
for v=V..0
for 所有的i屬於組k (我覺得循環順序應改成這樣,大家可以看一下以前的版本自己判斷)
f[v]=max{f[v],f[v-c]+w}
另外,顯然可以對每組中的物品應用P02中「一個簡單有效的優化」。
簡化問題
這種背包問題的物品間存在某種「依賴」的關係。也就是說,i依賴於j,表示若選物品i,則必須選物品j。為了簡化起見,我們先設沒有某個物品既依賴於別的物品,又被別的物品所依賴;另外,沒有某件物品同時依賴多件物品。
一般問題
更一般的問題是:依賴關係以圖論中「森林」的形式給出(森林即多叉樹的集合),也就是說,主件的附件仍然可以具有自己的附件集合,限制只是每個物品最多只依賴於一個物品(只有一個主件)且不出現循環依賴。
解決這個問題仍然可以用將每個主件及其附件集合轉化為物品組的方式。唯一不同的是,由於附件可能還有附件,就不能將每個附件都看作一個一般的01 背包中的物品了。若這個附件也有附件集合,則它必定要被先轉化為物品組,然後用分組的背包問題解出主件及其附件集合所對應的附件組中各個費用的附件所對應的價值。
事實上,這是一種樹形DP,其特點是每個父節點都需要對它的各個兒子的屬性進行一次DP以求得自己的相關屬性。這已經觸及到了「泛化物品」的思想。看完P08后,你會發現這個「依賴關係樹」每一個子樹都等價於一件泛化物品,求某節點為根的子樹對應的泛化物品相當於求其所有兒子的對應的泛化物品之和。
定義
考慮這樣一種物品,它並沒有固定的費用和價值,而是它的價值隨著你分配給它的費用而變化。這就是泛化物品的概念。
更嚴格的定義之。在背包容量為V的背包問題中,泛化物品是一個定義域為0..V中的整數的函數h,當分配給它的費用為v時,能得到的價值就是h(v)。
這個定義有一點點抽象,另一種理解是一個泛化物品就是一個數組h[0..V],給它費用v,可得到價值h[V]。
一個費用為c價值為w的物品,如果它是01背包中的物品,那麼把它看成泛化物品,它就是除了h(c)=w其它函數值都為0的一個函數。如果它是完全背包中的物品,那麼它可以看成這樣一個函數,僅當v被c整除時有h(v)=v/c*w,其它函數值均為0。如果它是多重背包中重複次數最多為n的物品,那麼它對應的泛化物品的函數有h(v)=v/c*w僅當v被c整除且v/c<=n,其它情況函數值均為0。
一個物品組可以看作一個泛化物品h。對於一個0..V中的v,若物品組中不存在費用為v的的物品,則h(v)=0,否則h(v)為所有費用為v的物品的最大價值。P07中每個主件及其附件集合等價於一個物品組,自然也可看作一個泛化物品。
問題泛化
一個背包問題中,可能會給出很多條件,包括每種物品的費用、價值等屬性,物品之間的分組、依賴等關係等。但肯定能將問題對應於某個泛化物品。也就是說,給定了所有條件以後,就可以對每個非負整數v求得:若背包容量為v,將物品裝入背包可得到的最大價值是多少,這可以認為是定義在非負整數集上的一件泛化物品。這個泛化物品——或者說問題所對應的一個定義域為非負整數的函數——包含了關於問題本身的高度濃縮的信息。一般而言,求得這個泛化物品的一個子域(例如0..V)的值之後,就可以根據這個函數的取值得到背包問題的最終答案。
綜上所述,一般而言,求解背包問題,即求解這個問題所對應的一個函數,即該問題的泛化物品。而求解某個泛化物品的一種方法就是將它表示為若干泛化物品的和然後求之。
輸出方案
一般而言,背包問題是要求一個最優值,如果要求輸出這個最優值的方案,可以參照一般動態規劃問題輸出方案的方法:記錄下每個狀態的最優值是由狀態轉移方程的哪一項推出來的,換句話說,記錄下它是由哪一個策略推出來的。便可根據這條策略找到上一個狀態,從上一個狀態接著向前推即可。
還是以01背包為例,方程為f[v]=max{f[v],f[v-c]+w}。再用一個數組g [v],設g[v]=0表示推出f[v]的值時是採用了方程的前一項(也即f[v]=f[v]),g[v]表示採用了方程的后一項。注意這兩項分別表示了兩種策略:未選第i個物品及選了第i個物品。那麼輸出方案的偽代碼可以這樣寫(設最終狀態為f[N][V]):
i=N
v=V
while(i>0)
if(g[v]==0)
print "未選第i項物品"
else if(g[v]==1)
print "選了第i項物品"
v=v-c
另外,採用方程的前一項或后一項也可以在輸出方案的過程中根據f[v]的值實時地求出來,也即不須紀錄g數組,將上述代碼中的g [v]==0改成f[v]==f[v],g[v]==1改成f[v]==f[v-c]+w也可。
輸出字典序最小的最優方案
這裡「字典序最小」的意思是1..N號物品的選擇方案排列出來以後字典序最小。以輸出01背包最小字典序的方案為例。
一般而言,求一個字典序最小的最優方案,只需要在轉移時注意策略。首先,子問題的定義要略改一些。我們注意到,如果存在一個選了物品1的最優方案,那麼答案一定包含物品1,原問題轉化為一個背包容量為v-c[1],物品為2..N的子問題。反之,如果答案不包含物品1,則轉化成背包容量仍為V,物品為2..N的子問題。不管答案怎樣,子問題的物品都是以i..N而非前所述的1..i的形式來定義的,所以狀態的定義和轉移方程都需要改一下。但也許更簡易的方法是先把物品逆序排列一下,以下按物品已被逆序排列來敘述。
在這種情況下,可以按照前面經典的狀態轉移方程來求值,只是輸出方案的時候要注意:從N到1輸入時,如果f[v]==f及f[v]==f[f-c]+w同時成立,應該按照後者(即選擇了物品i)來輸出方案。
最優方案
這裡的最優方案是指物品總價值最大的方案。還是以01背包為例。
結合求最大總價值和方案總數兩個問題的思路,最優方案的總數可以這樣求:f[v]意義同前述,g[v]表示這個子問題的最優方案的總數,則在求f[v]的同時求g[v]的偽代碼如下:
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c]+w}
g[v]=0
if(f[v]==f[v])
inc(g[v],g[v]
if(f[v]==f[v-c]+w)
inc(g[v],g[v-c])
如果你是第一次看到這樣的問題,請仔細體會上面的偽代碼。

小結

顯然,這裡不可能窮盡背包類動態規劃問題所有的問法。甚至還存在一類將背包類動態規劃問題與其它領域(例如數論、圖論)結合起來的問題,在這篇論背包問題的專文中也不會論及。但只要深刻領會前述所有類別的背包問題的思路和狀態轉移方程,遇到其它的變形問法,只要題目難度還屬於NOIP,應該也不難想出演算法。
觸類旁通、舉一反三,應該也是一個OIer應有的品質吧。
上一篇[裝箱問題]    下一篇 [單峰函數]

相關評論

同義詞:暫無同義詞