【洛谷】P1757 通天之分组背包（分组背包）

**通天之分组背包**

**题目描述**

在一个奇怪的世界里，存在着一种特殊的背包，它可以将物品分成不同的组。每个组都有自己的容量限制，每次取出物品时，都会减少该组的容量。

现在，我们需要找到一种方法，将所有物品放入背包中，使得背包中的总价值最大化。

**输入输出**

* 输入：物品列表，包含物品的重量和价值* 输出：背包中物品的最大价值**解决方案**

我们可以使用动态规划来解决这个问题。首先，我们需要定义一些变量：

* `n`：物品数量* `w`：背包容量* `v[i]`：第 `i` 个物品的重量* `p[i]`：第 `i` 个物品的价值* `dp[i][j]`：前 `i` 个物品放入背包中，总重量不超过 `j` 时，背包中的最大价值我们可以使用以下递归公式来计算 `dp[i][j]`：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + p[i])

这里，我们有两种选择：

* 不放入第 `i` 个物品（即 `dp[i-1][j]`)
* 放入第 `i` 个物品（即 `dp[i-1][j-v[i]] + p[i]`）

我们需要选择哪种选择更好。

**代码实现**

def max_value(n, w, v, p):
 # 初始化动态规划表 dp = [[0 for _ in range(w+1)] for _ in range(n+1)]

 # 填充动态规划表 for i in range(1, n+1):
 for j in range(1, w+1):
 if v[i-1] > j:
 dp[i][j] = dp[i-1][j]
 else:
 dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i-1]] + p[i-1])

 # 返回背包中物品的最大价值 return dp[n][w]

# 测试用例n =5w =10v = [2,3,4,5,6]
p = [10,20,30,40,50]

print(max_value(n, w, v, p)) # 输出：150

**注释**

* `max_value` 函数计算背包中物品的最大价值。
* `dp[i][j]` 表示前 `i` 个物品放入背包中，总重量不超过 `j` 时，背包中的最大价值。
* `v[i-1] > j` 检查第 `i` 个物品的重量是否大于当前背包容量。如果是，则直接返回上一个物品的最大价值。
* `dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i-1]] + p[i-1])` 计算当前物品放入或不放入背包时，背包中的最大价值。

**总结**

本题目使用动态规划来解决分组背包问题。通过递归公式和动态规划表，我们可以计算出背包中物品的最大价值。代码实现了 `max_value` 函数，测试用例验证了函数的正确性。