存在多背包且多种类物品的多重背包问题 python代码

# 多重背包问题中，存在多种类的物品和多个背包。
# 每个物品有一个重量和一个价值，每个背包有一个容量。
# 目标是在不超过每个背包容量的前提下，使得每个背包内的物品价值最大化。

def multiple_knapsack(N, M, c, w, v):
    """
    最大价值，dp[j]表示容量为j时背包内能取到的最大价值
    Args:
        N: 背包种类数
        M: 背包容量
        c: c[i][j]表示第i个物品在第j个背包中的数量上限
        w: 每个物品的重量
        v: 每个物品的价值
    Returns:
        dp[-1]: 总共能够获得的最大价值
    """
    dp = [0 for _ in range(M + 1)]
    for i in range(N):
        temp = [0 for _ in range(M + 1)]
        # 针对第i个物品的数量上限c[i]，考虑用01背包的形式求取
        for k in range(c[i] + 1):
            for j in range(M, -1, -1):
                if j >= k * w[i]:
                    temp[j] = max(temp[j], dp[j - k * w[i]] + k * v[i])
                else:
                    break
        # temp表示以第i个物品为参考，获得的最大价值
        # 然后将temp加入到背包总状态的dp列表中
        for j in range(M, -1, -1):
            for t in range(min(j, c[i] * w[i]), -1, -1):
                dp[j] = max(dp[j], temp[j - t] + dp[t])

    return dp[-1]

# 测试
N = 3  # 物品种类数
M = 10  # 背包容量
c = [[1, 2, 1], [2, 1, 2], [2, 2, 2]]  # 物品数量上限
w = [2, 3, 4]  # 物品重量
v = [15, 20, 30]  # 物品价值

ans = multiple_knapsack(N, M, c, w, v)
print(ans)  # 95