完全背包問題

題目：

有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路

這個問題非常類似于01背包問題，所不同的是每種物品有無限件。也就是從每種物品的角度考慮，與它相關的政策已并非取或不取兩種，而是有取0件、取1件、取2件……等很多種。如果仍然按照解01背包時的思路，令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值。仍然可以按照每種物品不同的政策寫出狀态轉移方程，像這樣：

這跟01背包問題一樣有O(VN)個狀态需要求解，但求解每個狀态的時間已經不是常數了，求解狀态f[i][v]的時間是O(v/c[i])，總的複雜度可以認為是O(V*Σ(V/c[i]))，是比較大的。

将01背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明01背包問題的方程的确是很重要，可以推及其它類型的背包問題。但我們還是試圖改進這個複雜度。

一個簡單有效的優化

完全背包問題有一個很簡單有效的優化，是這樣的：若兩件物品i、j滿足c[i]=w[j]，則将物品j去掉，不用考慮。這個優化的正确性顯然：任何情況下都可将價值小費用高得j換成物美價廉的i，得到至少不會更差的方案。對于随機生成的資料，這個方法往往會大大減少物品的件數，進而加快速度。然而這個并不能改善最壞情況的複雜度，因為有可能特别設計的資料可以一件物品也去不掉。

考慮到第i種物品最多選V/c[i]件，于是可以把第i種物品轉化為V/c[i]件費用及價值均不變的物品，然後求解這個01背包問題。這樣完全沒有改進基本思路的時間複雜度，但這畢竟給了我們将完全背包問題轉化為01背包問題的思路：将一種物品拆成多件物品。

更高效的轉化方法是：把第i種物品拆成費用為c[i]*2^k、價值為w[i]*2^k的若幹件物品，其中k滿足c[i]*2^k<=V。這是二進制的思想，因為不管最優政策選幾件第i種物品，總可以表示成若幹個2^k件物品的和。這樣把每種物品拆成O(log V/c[i])件物品，是一個很大的改進。

這個算法使用一維數組，先看僞代碼：

for i=1..N

for v=cost..V

    f[v]=max{f[v],f[v-cost]+weight}
           

你會發現，這個僞代碼與P01的僞代碼隻有v的循環次序不同而已。

舉例來說：

有三種面值的優惠券：30,50,100，分别有任意個數。現在給定一個金額V，求最大可以優惠的金額是多少。

抽象來說，這個問題可以用完全背包問題來解決。完全背包問題可以看做是：

有3種物品和一個為V的背包，這三種物品的重量分别為{30,50,100}，價值也可以看做分别對應是{30,50,100}

是以，可以寫出算法複雜度為O(VN)的代碼如下：

public class Soution1 {
    public static void main(String[]args){
        int num=;
        int all=;
        bao[] baos=new bao[num];
        baos[]=new bao(,);//(weight,value)
        baos[]=new bao(,);
        baos[]=new bao(,);
        getMaxValue(baos,num,all);
    }
    //一維數組解決
    public static void getMaxValue(bao[] baos,int num,int all){
        int[] f=new int[all+];
        for(int i=;i<num;i++){
            for(int j=baos[i].weight;j<=all;j++){
                f[j]=Math.max(f[j],f[j-baos[i].weight]+baos[i].value);
            }
        }
        System.out.println(f[all]);
    }
}
//V=110,輸出110
//V=70,輸出60
//V=120,輸出120
//V=20,輸出0
           

和01背包的差別，這裡的内循環是順序的，而01背包是逆序的。

現在關鍵的是考慮：為何完全背包可以這麼寫？

在次我們先來回憶下，01背包逆序的原因？是為了是max中的兩項是前一狀态值，這就對了。

那麼這裡，我們順序寫，這裡的max中的兩項當然就是目前狀态的值了，為何？

因為每種背包都是無限的。當我們把i從1到N循環時，f[v]表示容量為v在前i種背包時所得的價值，這裡我們要添加的不是前一個背包，而是目前背包。是以我們要考慮的當然是目前狀态。

對于二維數組，更新的時候為res[i][j-w[k]]