上一節(jié)中，我們介紹了0-1背包問題，接下來，我們來學(xué)習(xí)一下背包問題的其他變形問題，今天要學(xué)習(xí)的是完全背包問題。

1、簡介

有 N 種物品和一個容量為 W 的背包，每種物品都有無限件可用。第 i 種物品的重量是 w[i]，價值是 v[i]。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大?？梢钥吹剑c0-1背包問題不同的地方時，完全背包問題允許一件物品無限次的出現(xiàn)。

2、基本思路

這個問題非常類似于 0-1 背包問題，所不同的是每種物品有無限件。也就是從每 種物品的角度考慮，與它相關(guān)的策略已并非取或不取兩種，而是有取 0 件、取 1 件、取 2 件??等很多種。如果仍然按照解 01 背包時的思路，令 f[i][w]表示 前 i 種物品恰放入一個容量為 w 的背包的最大權(quán)值。仍然可以按照每種物品不同 的策略寫出狀態(tài)轉(zhuǎn)移方程，像這樣:
f[i][w]=max{f[i-1][w-kw[i]]+kw[i]|0<=kw[i]<=w}
這跟 0-1 背包問題一樣有 O(NW)個狀態(tài)需要求解，但求解每個狀態(tài)的時間已經(jīng)不 是常數(shù)了，求解狀態(tài) f[i][v]的時間是 O(w/w[i])，總的復(fù)雜度是超過 O(WN)的。
將 0-1 背包問題的基本思路加以改進，得到了這樣一個清晰的方法。這說明 0-1 背包問題的方程的確是很重要，可以推及其它類型的背包問題。但我們還是試圖 改進這個復(fù)雜度。

3、簡單優(yōu)化

完全背包問題有一個很簡單有效的優(yōu)化，是這樣的:若兩件物品 i、j 滿足 w[i]<=w[j]且 v[i]>=v[j]，則將物品 j 去掉，不用考慮。這個優(yōu)化的正確性顯 然:任何情況下都可將價值小費用高得 j 換成物美價廉的 i，得到至少不會更差 的方案。對于隨機生成的數(shù)據(jù)，這個方法往往會大大減少物品的件數(shù)，從而加快 速度。然而這個并不能改善最壞情況的復(fù)雜度，因為有可能特別設(shè)計的數(shù)據(jù)可以 一件物品也去不掉。
這個優(yōu)化可以簡單的 O(N^2)地實現(xiàn)，一般都可以承受。另外，針對背包問題而 言，比較不錯的一種方法是:首先將費用大于 V 的物品去掉，然后使用類似計數(shù) 排序的做法，計算出費用相同的物品中價值最高的是哪個，可以 O(W+N)地完成 這個優(yōu)化.

4、轉(zhuǎn)化為0-1背包問題

既然 0-1 背包問題是最基本的背包問題，那么我們可以考慮把完全背包問題轉(zhuǎn)化 為 0-1 背包問題來解。最簡單的想法是，考慮到第 i 種物品最多選 W/w[i]件，于 是可以把第 i 種物品轉(zhuǎn)化為 W/w[i]件費用及價值均不變的物品，然后求解這個 0-1 背包問題。這樣完全沒有改進基本思路的時間復(fù)雜度，但這畢竟給了我們將 完全背包問題轉(zhuǎn)化為 0-1 背包問題的思路:將一種物品拆成多件物品。
更高效的轉(zhuǎn)化方法是:把第 i 種物品拆成費用為 w[i]2^k、價值為 v[i]2^k 的 若干件物品，其中 k 滿足 w[i]*2^k<=W。這是二進制的思想，因為不管最優(yōu)策略 選幾件第 i 種物品，總可以表示成若干個 2^k 件物品的和。這樣把每種物品拆成 O(log(W/w[i]))件物品，是一個很大的改進。

但我們有更優(yōu)的 O(VN)的算法。

5、O(VN)的算法

這個算法使用一維數(shù)組，先看偽代碼:

   for i=1..N
       for w=0..W
f[w]=max{f[w],f[w-cost]+weight}

你會發(fā)現(xiàn)，這個偽代碼與0-1背包問題只有 的循環(huán)次序不同而已。為什么這樣 一改就可行呢?首先想想為什么 0-1背包問題中要按照 w=W..0 的逆序來循環(huán)。這是因為 要保證第 i 次循環(huán)中的狀態(tài) f[i][w]是由狀態(tài) f[i-1][w-w[i]]遞推而來。換句話 說，這正是為了保證每件物品只選一次，保證在考慮“選入第 i 件物品”這件策 略時，依據(jù)的是一個絕無已經(jīng)選入第 i 件物品的子結(jié)果 f[i-1][w-w[i]]。而現(xiàn) 在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第 i 種物 品”這種策略時，卻正需要一個可能已選入第 i 種物品的子結(jié)果 f[i][w-w[i]]， 所以就可以并且必須采用 w=0..W 的順序循環(huán)。這就是這個簡單的程序為何成立 的道理。

6、完全背包問題Python實現(xiàn)

基于上面的思路，完全背包問題Python實現(xiàn)代碼如下：

def solve3(vlist,wlist,totalWeight,totalLength):
    """完全背包問題"""
    resArr = np.zeros((totalWeight)+1,dtype=np.int32)
    for i in range(1,totalLength+1):
        for j in range(1,totalWeight+1):
            if wlist[i] <= j:
                resArr[j] = max(resArr[j],resArr[j-wlist[i]]+vlist[i])
    return resArr[-1]

if __name__ == '__main__':
    v = [0,60,100,120]
    w = [0,10,20,30]
    weight = 50
    n = 3
    result = solve3(v,w,weight,n)
    print(result)