python 背包问题：0-1背包，多重背包，数据结构，超详细模板套用和解读；数组组合问题

一、0-1背包问题：

题目：有n个物品，第i个体积为w[i]，价值为v[i]，每个物品最多选一个，求体积和不超过capacity时能装物品的最大价值

转移方程：

dfs(i,c) = max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i])

含义：第i个物品的最大价值等于，（没有选择第i个物品时的价值）和（选择了第i个物品时的价值）中最大的哪一个。

def zero_one_knapsack(weight:List[int],value:List[int],capacity:int)->int:
    n = len(weight)
 
    def dfs(i,c):
        if i < 0:
            return 0
        if c < weight[i]:
            return dfs(i-1,c)
        return max(dfs(i-1,c),dfs(i-1,c-weight[i])+value[i])
    ans = dfs(n-1,capacity)
    return ans
 
weight = [1,3,5,6,7,8]
value = [5,4,3,2,1,1]
capacity = 10
print(zero_one_knapsack(weight,value,capacity))

（1）求最大价值：如上

（2）求方案数：需要更改约束条件和方程：

def dfs(i,c):
    if i < 0:
        return 1 if c==0 else 0
    if weight[i] < c:
        return dfs(i-1,c)
    return dfs(i-1,c) + dfs(i-1,c-weight[i])

方案数：数组递推形式：此时没有用到value数组：此种题目常见于数组组合达到target值的方案数

def zero_one_knapsack(weight:List[int],capacity:int)->int:
    n = len(weight)
    f = [[0] * (capacity + 1) for _ in range(n + 1)]
    f[0][0] = 1
    for i,x in enumerate(weight):
        for c in range(capacity + 1):
            if c < x:
                f[i+1][c] = f[i][c]
            else:
                f[i+1][c] = f[i][c] + f[i][c-x]
    return f[n][capacity]
 
weight = [1,3,5,6,7,8]
 
capacity = 10
print(zero_one_knapsack(weight,capacity))

空间优化：用二维矩阵表示

def zero_one_knapsack(weight:List[int],capacity:int)->int:
    n = len(weight)
    f = [[0] * (capacity + 1) for _ in range(2)]
    f[0][0] = 1
    for i,x in enumerate(weight):
        for c in range(capacity + 1):
            if c < x:
                f[(i+1)%2][c] = f[i%2][c]
            else:
                f[(i+1)%2][c] = f[i%2][c] + f[i%2][c-x]
    return f[n%2][capacity]

空间优化：用一维矩阵表示

def zero_one_knapsack(weight:List[int],capacity:int)->int:
    n = len(weight)
    f = [0] * (capacity + 1)
    f[0] = 1
    for x in weight:
        for c in range(capacity,x-1,-1):
            f[c] = f[c] + f[c-x]
    return f[capacity]

二、多重背包：就是不限制物品数量，同一个物品可以拿多次

转移方程：

dfs(i,c) = max(dfs(i-1,c),dfs(i,c-w[i])+v[i])

就是拿完i物品，还可以继续拿i，而不是递到i-1。

def dfs(i,c):
    if i < 0:
        return 0
    if c < w[i]:
        return dfs(i-1,c)
    return max(dfs(i-1,c),dfs(i,c-w[i])+v[i])