二维费用背包（既有最大体积限制，又多加了一个最大重量限制）

**二维费用背包**

在传统的背包问题中，我们需要在给定的物品集合中选择一组物品，使其总体积尽可能大，同时不超过最大体积限制。然而，在现实世界中，物品往往有多种属性，如重量、价值等，而不是仅仅考虑体积。因此，二维费用背包问题的出现，它结合了体积和重量两个因素，使得我们需要在选择物品时同时考虑这两个限制。

**问题描述**

假设我们有 n 个物品，每个物品都有一个体积（v_i）和一个重量（w_i），以及一个价值（p_i）。我们的目标是选择一组物品，使其总体积不超过最大体积限制 M，总重量不超过最大重量限制 W，同时使得总价值尽可能大。

**动态规划**

二维费用背包问题可以使用动态规划来解决。我们首先定义一个2D 数组 dp[n+1][M+1][W+1]，其中 dp[i][j][k] 表示前 i 个物品中选择的物品总体积为 j，总重量为 k 时的最大价值。

**状态转移方程**

对于每个物品 i，我们有以下几种情况：

* 如果物品 i 的体积大于当前最大体积 j 或重量大于当前最大重量 k，则不选择该物品，状态转移方程为：dp[i][j][k] = dp[i-1][j][k]
* 如果物品 i 的体积小于或等于当前最大体积 j且重量小于或等于当前最大重量 k，则有两种选择：
+ 不选择该物品，状态转移方程为：dp[i][j][k] = dp[i-1][j][k]
+选择该物品，状态转移方程为：dp[i][j][k] = max(dp[i-1][j-v_i][k-w_i]+p_i, dp[i-1][j][k])

**代码示例**

def two_dimensional_knapsack(n, M, W):
 # 初始化动态规划数组 dp = [[[0 for _ in range(W+1)] for _ in range(M+1)] for _ in range(n+1)]

 #读取物品信息 items = []
 for i in range(n):
 v_i, w_i, p_i = map(int, input().split())
 items.append((v_i, w_i, p_i))

 # 动态规划 for i in range(1, n+1):
 for j in range(M+1):
 for k in range(W+1):
 if items[i-1][0] > j or items[i-1][1] > k:
 dp[i][j][k] = dp[i-1][j][k]
 else:
 dp[i][j][k] = max(dp[i-1][j-items[i-1][0]][k-items[i-1][1]]+items[i-1][2], dp[i-1][j][k])

 # 返回最大价值 return dp[n][M][W]

# 测试用例n, M, W =5,10,15print(two_dimensional_knapsack(n, M, W))