物品数量有限的背包问题Python代码

动态规划实现0-1背包问题的代码如下：

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))

相关问题

存在多背包且多种类物品的多重背包问题 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

背包问题 python代码 及解释

背包问题是一个经典的动态规划问题，可以用来解决一些物品放入背包中的最优化问题。以下是一个 Python 代码示例及其解释：

def knapsack(capacity, weights, values, n):
    # 创建一个二维数组来存储子问题的解
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
    
    # 填充 dp 数组，从底部向上计算每个子问题的最优解
    for i in range(n + 1):
        for w in range(capacity + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]],  dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    # 返回最终问题的解
    return dp[n][capacity]

在这个代码中，`knapsack` 函数接受四个参数：`capacity` 表示背包的最大容量，`weights` 表示物品的重量，`values` 表示物品的价值，`n` 表示物品的数量。

在函数中，我们首先创建一个二维数组 `dp` 来存储子问题的最优解。接下来，我们使用两个嵌套的循环来填充 `dp` 数组。在每个子问题中，我们检查当前物品是否可以放入背包中。如果可以，我们考虑将该物品放入背包中，然后计算它的总价值。我们还需要考虑在不放置该物品的情况下，我们能够获得的最大价值。我们将这两个值中的较大值存储在 `dp` 数组中。如果该物品不能放入背包中，我们只需要使用之前已经计算过的最优解。

最后，我们返回 `dp[n][capacity]`，这是问题的最终解。