当前没有测试数据。

星际运输舱的物资装载

题目描述

在未来的星际空间站，运输舱需要为远征队运送物资到火星基地。每个物资箱有两个维度的限制：

• 重量限制：运输舱最大承重为 $W$ 千克
• 体积限制：运输舱最大容积为 $V$ 立方米

现有 $n$ 件物资，每件物资都有重量、体积和价值。每件物资只能选择装或不装，不能分割。你的任务是在不超过重量和体积双限制的前提下，使物资总价值最大。

输入格式

第一行包含三个整数 $n, W, V$，分别表示物资数量、重量限制和体积限制。

接下来 $n$ 行，每行包含三个整数 $w_i, v_i, c_i$，依次表示一件物资的重量（千克）、体积（立方米）和价值。

输出格式

输出一个整数，表示可以获得的最大总价值。

样例输入

5 10 8
2 1 3
3 3 4
4 2 5
5 4 6
1 2 2

样例输出

14

样例解释

最优方案是选择第1、2、3、5件物资：

• 总重量：2 + 3 + 4 + 1 = 10 ≤ 10
• 总体积：1 + 3 + 2 + 2 = 8 ≤ 8
• 总价值：3 + 4 + 5 + 2 = 14

这是最优解。

数据范围

• $1 \leq n \leq 100$
• $1 \leq W, V \leq 200$
• $1 \leq w_i \leq W$
• $1 \leq v_i \leq V$
• $1 \leq c_i \leq 1000$

提示

本题是标准的二维费用01背包问题。

设 $dp[i][j][k]$ 表示前 $i$ 件物资，在重量限制为 $j$、体积限制为 $k$ 时的最大价值。

状态转移方程：

$$dp[i][j][k] = \max(dp[i-1][j][k], dp[i-1][j-w_i][k-v_i] + c_i)$$

可以使用一维优化：

for (int i = 1; i <= n; i++) {
    for (int j = W; j >= w[i]; j--) {
        for (int k = V; k >= v[i]; k--) {
            dp[j][k] = max(dp[j][k], dp[j-w[i]][k-v[i]] + c[i]);
        }
    }
}

注意：两个维度都需要倒序遍历，以确保每件物资只被选一次。

进阶思考

如果要求恰好装满重量和体积（两个维度都恰好用完），应该如何修改代码？