完全背包問題

1、完全背包問題（無限背包）1 問題2 基本思路3 空間優(yōu)化4小結(jié)1 問題 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是wi，價值是ci。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。 2 基本思路 這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取0件、取1件、取2件等很多種。如果仍然按照解01背包時的思路，令fiv表示前i種物品恰放入一個容量為v的背包的最大權(quán)值。仍然可以按照每種物品不同的策略寫出狀態(tài)轉(zhuǎn)移方程： fiv=maxfi-1v-k*wi+k*ci

2、|0=k*wi= v。 將01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。核心代碼： for i=1.N for v=0.V for k=1.v div wi fiv=maxfi-1v,fi-1v-k*wi+k*ci; 你會發(fā)現(xiàn)，這個偽代碼與01背包問題的偽代碼只有v的循環(huán)次序不同而已。為什么這樣一改就可行呢？首先想想為什么01背包問題中要按照v=V.0的逆序來循環(huán)。這是因為要保證第i次循環(huán)中的狀態(tài)fiv是由狀態(tài)fi-1v-wi遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，

3、依據(jù)的是一個絕無已經(jīng)選入第i件物品的子結(jié)果fi-1v-wi。而現(xiàn)在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結(jié)果fiv-wi，所以就可以并且必須采用v= 0.V的順序循環(huán)。這就是這個簡單的程序為何成立的道理。 這個算法也可以以另外的思路得出。例如，基本思路中的狀態(tài)轉(zhuǎn)移方程可以等價地變形成這種形式：fiv=maxfi-1v,fiv-wi+ci，將這個方程用一維數(shù)組實現(xiàn)，便得到了上面的核心代碼。3 空間優(yōu)化01背包中，我們使用一維數(shù)組來優(yōu)化空間，完全背包中同樣可以！這個算法使用一維數(shù)組，核心代碼如下： for i=1.N

4、for v=0.V fv=maxfv,fv-wi+ci; 【問題描述】 設(shè)有n種物品，每種物品有一個重量及一個價值。但每種物品的數(shù)量是無限的，同時有一個背包，最大載重量為M，今從n種物品中選取若干件(同一種物品可以多次選取)，使其重量的和小于等于M，而價值的和為最大?！据斎敫袷健?第一行：兩個整數(shù)，M(背包容量，M=200)和N(物品數(shù)量，N=30)； 第2.N+1行：每行二個整數(shù)Wi,Ci，表示每個物品的重量和價值。 【輸出格式】 僅一行，一個數(shù)，表示最大總價值。【樣例輸入】knapsack.in10 42 13 34 57 9【樣例輸出】knapsack.outmax=12【解法一：二維數(shù)

5、組】【算法分析】設(shè) f(i，x)表示前i件物品，總重量不超過x的最優(yōu)價值，則 f(i，x)=max(f(i，x-wi)+ci,f(i-1，x) ；f（n，m）即為最優(yōu)解?！緟⒖汲绦颉?（順推法）Program knapsack;Const maxm=200;maxn=30;var i,x,n,m:integer; w,c:array1.maxn of integer; f:array0.maxn,0.maxm of integer;BEGINfillchar(w,sizeof(w),0); fillchar(c,sizeof(c),0); readln(m,n); /背包容量m和物品數(shù)量n f

6、or i:=1 to n do /每個物品的重量和價值 read(wi,ci); for i:=1 to n do /f(i，x)表示前i件物品，總重量不超過x的最優(yōu)價值 for x:=1 to m do if xfi,x-wi+ci then fi,x:=fi-1,x else fi,x:=fi,x-wi+ci; writeln(max=, fn,m); / f(n，m)為最優(yōu)解END.【解法一：一維數(shù)組】【算法分析】 本問題的數(shù)學(xué)模型如下： 設(shè) f(x)表示重量不超過x公斤的最大價值， 則 f(x)=maxf(x-wi)+ci 當(dāng)x=wi ，1=i=wi then if fx-wi+cif

7、x then fx:= fx-wi+ci ; writeln(max=,fm); / f(m)為最優(yōu)解END.【參考程序2】:（順推法） program knapsack04;const maxm=200;maxn=30;type ar=array0.maxn of integer;var m,n,x,i,t:integer; c,w:ar; f:array0.maxm of integer;BEGINreadln(m,n); /背包容量m和物品數(shù)量n for i:= 1 to n do readln(wi,ci); /每個物品的重量和價值 f0:=0; for i:=1 to n do for x:=1 to m do /設(shè) f(x)表示重量不超過x公斤的最大價值 if x=wi then if fx-wi+cifx then fx:= fx-wi+ci ; writeln(max=,fm); / f(m)為最優(yōu)解END.上面的代碼中兩層for循環(huán)的次序可以顛倒 4小結(jié) 完全背包問題也是一個相當(dāng)基礎(chǔ)的背包問題，它有兩個狀態(tài)轉(zhuǎn)移方程：fiv=maxfi-1v-k*wi+k*ci|0=k*