完全背包問題：
有n個(gè)重量分別為{w1，w2，…，wn}的物品，它們的價(jià)值分別為{v1，v2，…，vn}，給定一個(gè)容量為W的背包。小偷要選擇從這些物品中偷一部分物品放入該背包的方案，每個(gè)物品可以偷任意個(gè)，要求選中的物品不僅能夠放到背包中，而且重量和為W具有最大的價(jià)值。
該題是0-1背包問題的擴(kuò)展，0-1背包是某個(gè)物品偷或者不偷，完全背包是某個(gè)物品要偷多少個(gè)？
從0-1背包問題那我們推斷出了一個(gè)狀態(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件物品價(jià)值
對(duì)該公式不明白的可以參考我前面寫的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背包問題寫一個(gè)三層嵌套循環(huán)，然而寫起來并不優(yōu)美，這個(gè)式子其實(shí)可以再簡化，我們推導(dǎo)一下：

1. 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'只是一個(gè)新的系數(shù)表示
2. 這樣一來，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]
3. 另外（1）式可以表示為：B(i,w) = max( B(i-1,w-c(i)* k)+v(i)* k ) ：0=<k<=[V/c(i)]
4. 同樣 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）式的右邊和上面這個(gè)（4）式的右邊是一摸一樣的，所以得到了簡化式
   B(i,w) =max( B(i-1,w), B(i,w-c(i)) + v(i))
   時(shí)間復(fù)雜度減少了，因?yàn)樯倭艘粋€(gè)嵌套循環(huán)

還可以優(yōu)化下空間復(fù)雜度。就像0-1背包問題一樣，我們做一維滾動(dòng)數(shù)組優(yōu)化。因?yàn)锽(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)]

偽代碼：

請(qǐng)注意for v = c[i] ... V 這和0-1背包問題是反向的因?yàn)锽(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)一維你需要了解一下滾動(dòng)數(shù)組這個(gè)東西，然后完全背包的二維公式是 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)這個(gè)式子，y對(duì)應(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};  //每個(gè)商品容量
    private static final int v[]={3,4,5,8,10}; //每個(gè)商品價(jià)值

    public static void main(String[] args) {
        KnapSack knapSack = new KnapSack();
        int bfull[] = knapSack.callFull();
        System.out.println(bfull[20);

    }
     //完全背包  ...
    public int[] callFull(){
        //計(jì)算用
        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;
    }