揹包問題基礎知識

問題 ： 給定一組專案，其中每個專案包含權重和值，確定要包含在集合中的每個專案的數量，以便總權重小於或等於給定限制，並且總值儘可能大。

揹包問題的虛擬碼

鑑於：

1. 值（陣列 v）
2. 重量（陣列 w）
3. 不同專案數量（n）
4. 量（W）

for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

使用 Python 簡單實現上面的虛擬碼：

def knapSack(W, wt, val, n):
    K = [[0 for x in range(W+1)] for x in range(n+1)]
    for i in range(n+1):
        for w in range(W+1):
            if i==0 or w==0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                K[i][w] = K[i-1][w]
    return K[n][W]
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(knapSack(W, wt, val, n))

執行程式碼：將其儲存在名為 knapSack.py 的檔案中

$ python knapSack.py
220

上述程式碼的時間複雜度：O(nW) 其中 n 是專案數，W 是揹包的容量。