背包问题基础知识

问题 ： 给定一组项目，其中每个项目包含权重和值，确定要包含在集合中的每个项目的数量，以便总权重小于或等于给定限制，并且总值尽可能大。

背包问题的伪代码

鉴于：

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 是背包的容量。