多重背包问题

多重背包问题

问题描述

多重背包问题是一个经典的动态规划问题。在这个问题中，我们有 N 件物品，每件物品都有一个体积、一个价值和一个数量上限。我们的目标是将这些物品放入一个容量为 V 的背包中，使得背包中的物品总价值最大。

动态规划思路

我们使用动态规划来解决这个问题。定义 dp[i][j] 表示前 i 件物品恰好放入一个容量为 j 的背包可以获得的最大价值。

状态转移方程

状态转移方程为：

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-k * wi] + k * vi)

其中 0 <= k <= si，wi 是第 i 件物品的体积，vi 是第 i 件物品的价值，si 是第 i 件物品的数量上限。

原始代码实现

以下是原始的多重背包问题的代码实现：

1
2
3
4
5
6
7
8
9
N, V = map(int, input().split())
dp = [[0] * (V + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    # 体积，价值，数量
    wi, vi, si = map(int, input().split())
    for j in range(V + 1):
        for k in range(0, min(j // wi, si) + 1):
            dp[i][j] = max(dp[i][j], dp[i - 1][j - k * wi] + k * vi)
print(dp[N][V])

优化：二进制拆分

为了优化上述算法，我们可以使用二进制拆分的方法，将物品的数量转化为多个物品。这样可以减少状态转移的复杂度。

优化代码实现

以下是优化后的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
N, V = map(int, input().split())
w = []
v = []

for i in range(N):
    wi, vi, si = map(int, input().split())
    k = 1
    while k <= si:
        w.append(wi * k)
        v.append(vi * k)
        si -= k
        k *= 2
    if si != 0:
        w.append(wi * si)
        v.append(vi * si)

# dp数组
dp = [0] * (V + 1)

# 动态规划
for i in range(len(w)):
    for j in range(V, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])

# 输出结果
print(dp[V])

总结

通过动态规划和二进制拆分的方法，我们可以有效地解决多重背包问题。优化后的代码在处理大规模数据时表现更佳，减少了计算复杂度。