完全背包問題：
有n個重量分別為{w1，w2赁咙，…钮莲，wn}的物品免钻，它們的價值分別為{v1，v2崔拥，…极舔，vn}，給定一個容量為W的背包链瓦。小偷要選擇從這些物品中偷一部分物品放入該背包的方案拆魏，每個物品可以偷任意個，要求選中的物品不僅能夠放到背包中慈俯，而且重量和為W具有最大的價值渤刃。
該題是0-1背包問題的擴(kuò)展，0-1背包是某個物品偷或者不偷贴膘，完全背包是某個物品要偷多少個溪掀？
從0-1背包問題那我們推斷出了一個狀態(tài)轉(zhuǎn)移公式：
B(i,w) = max( B(i-1,w) ,B(i-1,w-c(i))+v(i) )
其中,i=前i件物品，w=可用容量 c(i)=第i件物品容量步鉴，v(i)=第i件物品價值
對該公式不明白的可以參考我前面寫的0-1背包問題DP
所以揪胃，我們很容易推導(dǎo)出完全背包問題的狀態(tài)轉(zhuǎn)移公式：
B(i,w) = max( B(i-1,w) ,B(i-1,w-c(i)*k)+v(i)*k ) 1=<k<=[V/c(i)] ,V為總可用容量，是w的最大值
如此氛琢，我們可以模擬0-1背包問題寫一個三層嵌套循環(huán)喊递，然而寫起來并不優(yōu)美，這個式子其實(shí)可以再簡化阳似，我們推導(dǎo)一下：
-
B(i,w) = max( B(i-1,w) ,B(i-1,w-c(i)* k)+v(i)* k ) ：1=<k<=[V/c(i)]我們觀察B(i-1,w-c(i)* k)+v(i)* k 讓 k=k'+1骚勘，或者你也可以取k=x+1,k=y+1都行，k'只是一個新的系數(shù)表示 -
這樣一來撮奏，B(i-1,w-c(i)* k)+v(i)* k ：1=<k<=[V/c(i)]轉(zhuǎn)換到<==>B(i-1,w-c(i)-c(i)* k')+v(i)* k'+v(i) ：0=<k'<=[V/c(i) -1] 另外（1）式可以表示為：B(i,w) = max( B(i-1,w-c(i)* k)+v(i)* k ) ：0=<k<=[V/c(i)]-
同樣 B(i,w-c(i)) = max( B(i-1,w-c(i)-c(i)* k)+v(i)* k ) ： 0=<k<=[V/c(i)-1]
觀察一下俏讹，（2）式的右邊和上面這個（4）式的右邊是一摸一樣的，所以得到了簡化式
B(i,w) =max( B(i-1,w), B(i,w-c(i)) + v(i))
時間復(fù)雜度減少了畜吊，因為少了一個嵌套循環(huán)
還可以優(yōu)化下空間復(fù)雜度泽疆。就像0-1背包問題一樣，我們做一維滾動數(shù)組優(yōu)化玲献。因為B(i,w)僅僅依賴于B(i-1,w)和B(i,w-c(i));
最終得到 B(w) =max( B(w), B(w-c(i)) + v(i)) 1=<k<=[V/c(i)]
偽代碼：
請注意for v = c[i] ... V 這和0-1背包問題是反向的因為B(i,w)用到了B(i,w-c(i));新值哦
for v = 0 ... V do B[v] = 0
for i = 1 ... N do
for w = c[i] ... V do
B[w] = max{B[w], B[w-c[i]] + v[i]}
二維轉(zhuǎn)一維你需要了解一下滾動數(shù)組這個東西殉疼，然后完全背包的二維公式是 B(i,w) =max( B(i-1,w), B(i,w-c(i)) + v(i)) ，下標(biāo)有i代表的都是新值捌年，有i-1代表的都是舊值瓢娜，轉(zhuǎn)成一維后是 B(w) =max( B(w), B(w-c(i)) + v(i)) ，當(dāng)然如果要理解順序問題的話得這么寫： B(w)新 =max( B(w)舊, B(w-c(i))新 + v(i)) 礼预，你想下x=max(x,y)這個式子眠砾，y對應(yīng)B(w-c(i)),x是B(w)。w-c(i)比w小托酸，所以要先處理小的褒颈，循環(huán)從小往大更新
上Java代碼:
/**
* @author JaJIng
*/
class KnapSack{
private static final int N = 5;//商品種類
private static final int C = 20;//總可用容量
private static final int w[]={2,3,4,5,9}; //每個商品容量
private static final int v[]={3,4,5,8,10}; //每個商品價值
public static void main(String[] args) {
KnapSack knapSack = new KnapSack();
int bfull[] = knapSack.callFull();
System.out.println(bfull[20);
}
//完全背包 ...
public int[] callFull(){
//計算用
int B[] = new int[C+1];
for(int n=0;n<N;n++){
for(int c=w[n];c<=C;c++){
B[c] = Math.max(B[c],B[c-w[n]]+v[n]);
}
}
return B;
}
