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

1眯牧、簡介

有 N 種物品和一個(gè)容量為 W 的背包蹋岩，每種物品都有無限件可用。第 i 種物品的重量是 w[i]学少，價(jià)值是 v[i]剪个。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價(jià)值總和最大旱易〗耍可以看到腿堤，與0-1背包問題不同的地方時(shí)阀坏，完全背包問題允許一件物品無限次的出現(xiàn)。

2笆檀、基本思路

這個(gè)問題非常類似于 0-1 背包問題忌堂，所不同的是每種物品有無限件。也就是從每 種物品的角度考慮酗洒，與它相關(guān)的策略已并非取或不取兩種士修，而是有取 0 件、取 1 件樱衷、取 2 件??等很多種棋嘲。如果仍然按照解 01 背包時(shí)的思路，令 f[i][w]表示 前 i 種物品恰放入一個(gè)容量為 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)個(gè)狀態(tài)需要求解，但求解每個(gè)狀態(tài)的時(shí)間已經(jīng)不 是常數(shù)了侄榴，求解狀態(tài) f[i][v]的時(shí)間是 O(w/w[i])雹锣，總的復(fù)雜度是超過 O(WN)的。
將 0-1 背包問題的基本思路加以改進(jìn)癞蚕，得到了這樣一個(gè)清晰的方法蕊爵。這說明 0-1 背包問題的方程的確是很重要，可以推及其它類型的背包問題桦山。但我們還是試圖 改進(jìn)這個(gè)復(fù)雜度攒射。

3醋旦、簡單優(yōu)化

完全背包問題有一個(gè)很簡單有效的優(yōu)化，是這樣的:若兩件物品 i会放、j 滿足 w[i]<=w[j]且 v[i]>=v[j]浑度，則將物品 j 去掉，不用考慮鸦概。這個(gè)優(yōu)化的正確性顯 然:任何情況下都可將價(jià)值小費(fèi)用高得 j 換成物美價(jià)廉的 i箩张，得到至少不會(huì)更差 的方案。對(duì)于隨機(jī)生成的數(shù)據(jù)窗市，這個(gè)方法往往會(huì)大大減少物品的件數(shù)先慷，從而加快 速度。然而這個(gè)并不能改善最壞情況的復(fù)雜度咨察，因?yàn)橛锌赡芴貏e設(shè)計(jì)的數(shù)據(jù)可以 一件物品也去不掉论熙。
這個(gè)優(yōu)化可以簡單的 O(N^2)地實(shí)現(xiàn)，一般都可以承受摄狱。另外脓诡，針對(duì)背包問題而 言，比較不錯(cuò)的一種方法是:首先將費(fèi)用大于 V 的物品去掉媒役，然后使用類似計(jì)數(shù) 排序的做法祝谚，計(jì)算出費(fèi)用相同的物品中價(jià)值最高的是哪個(gè)，可以 O(W+N)地完成 這個(gè)優(yōu)化.

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

既然 0-1 背包問題是最基本的背包問題交惯，那么我們可以考慮把完全背包問題轉(zhuǎn)化 為 0-1 背包問題來解。最簡單的想法是穿仪，考慮到第 i 種物品最多選 W/w[i]件席爽，于 是可以把第 i 種物品轉(zhuǎn)化為 W/w[i]件費(fèi)用及價(jià)值均不變的物品，然后求解這個(gè) 0-1 背包問題啊片。這樣完全沒有改進(jìn)基本思路的時(shí)間復(fù)雜度只锻，但這畢竟給了我們將 完全背包問題轉(zhuǎn)化為 0-1 背包問題的思路:將一種物品拆成多件物品。
更高效的轉(zhuǎn)化方法是:把第 i 種物品拆成費(fèi)用為 w[i]2^k紫谷、價(jià)值為 v[i]2^k 的 若干件物品齐饮，其中 k 滿足 w[i]*2^k<=W。這是二進(jìn)制的思想碴里，因?yàn)椴还茏顑?yōu)策略 選幾件第 i 種物品沈矿，總可以表示成若干個(gè) 2^k 件物品的和。這樣把每種物品拆成 O(log(W/w[i]))件物品咬腋，是一個(gè)很大的改進(jìn)羹膳。

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

5根竿、O(VN)的算法

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

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

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

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

基于上面的思路选侨，完全背包問題Python實(shí)現(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)