题解 | #星际勘探任务#

题目链接

星际勘探任务

题目描述

一名星际探险家计划勘探 $N$ 个星球。飞船的总续航时间上限为 $M$ ，总能量储备上限为 $K$ 。对于第 $i$ 个星球，勘探需要花费时间 $T_i$ ，消耗能量 $E_i$ ，并能获得价值 $V_i$ 的科学数据。

请求出在总续航时间和总能量消耗不超过上限的前提下，探险家能获得的最大科学数据总价值。

解题思路

这是一个典型的二维 0/1 背包问题。

问题抽象
- 物品： $N$ 个星球。
- 背包容量：这是一个有两维限制的背包，第一维是总续航时间 $M$ ，第二维是总能量储备 $K$ 。
- 物品的“重量”：每个星球 $i$ 也有两维的“重量”或成本，即勘探所需时间 $T_i$ 和所需能量 $E_i$ 。
- 物品的价值：每个星球 $i$ 的价值是 $V_i$ 。
- 目标：选择若干物品放入背包，使得它们的两维“重量”之和分别不超过背包的两维容量，同时最大化所选物品的总价值。
动态规划 (DP) 求解
- 状态定义：我们定义一个二维 DP 数组 dp[t][e]，表示：在续航时间上限为 $t$ 、能量储备上限为 $e$ 的约束下，所能获得的最大科学数据总价值。
- 状态转移方程：我们遍历每一个星球（物品）。对于当前的星球 $i$ （其属性为 $T_i, E_i, V_i$ ），我们更新整个 dp 表。对于每一个状态 dp[t][e]，我们有两种决策：
  1. 不勘探星球 $i$ ：最大价值保持不变，仍然是考虑前 $i-1$ 个星球时的 dp[t][e]。
  2. 勘探星球 $i$ ：这个决策是可行的，当且仅当 $t \ge T_i$ 且 $e \ge E_i$ 。如果可行，那么勘探后的价值将是 $V_i$ 加上在扣除该星球消耗后、剩余容量 $(t-T_i, e-E_i)$ 下能获得的最大价值，即 dp[t - T_i][e - E_i] + V_i。
  我们将这两种决策的更优者作为新的 dp[t][e] 的值。因此，状态转移方程为： dp[t][e] = max(dp[t][e], dp[t - T_i][e - E_i] + V_i)
- 实现细节与空间优化：
  - 和标准的 0/1 背包问题一样，我们可以进行空间优化。dp 数组的维度可以降至二维，即 dp[t][e]。
  - 为了确保每个星球（物品）只被选择一次（即符合 0/1 背包的特性），我们需要在遍历背包容量时从大到小（倒序）进行。这样可以保证在计算 dp[t][e] 时，所依赖的 dp[t - T_i][e - E_i] 存储的是处理当前星球之前的旧值。
- 初始化：创建一个大小为 $(M+1) \times (K+1)$ 的 dp 数组，并将其所有元素初始化为 0。
- 最终答案：遍历完所有星球后，dp[M][K] 中存储的就是在满足所有约束条件下的最大总价值。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Planet {
    int time, energy, value;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int max_time, max_energy;
    cin >> max_time >> max_energy;

    vector<Planet> planets(n);
    for (int i = 0; i < n; ++i) {
        cin >> planets[i].time >> planets[i].energy >> planets[i].value;
    }

    // dp[t][e] 表示时间上限t，能量上限e时的最大价值
    vector<vector<int>> dp(max_time + 1, vector<int>(max_energy + 1, 0));

    // 遍历每个星球
    for (int i = 0; i < n; ++i) {
        // 倒序遍历时间和能量，确保每个物品只用一次
        for (int t = max_time; t >= planets[i].time; --t) {
            for (int e = max_energy; e >= planets[i].energy; --e) {
                dp[t][e] = max(dp[t][e], dp[t - planets[i].time][e - planets[i].energy] + planets[i].value);
            }
        }
    }

    cout << dp[max_time][max_energy] << "\n";

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int maxTime = sc.nextInt();
        int maxEnergy = sc.nextInt();

        int[] times = new int[n];
        int[] energies = new int[n];
        int[] values = new int[n];

        for (int i = 0; i < n; i++) {
            times[i] = sc.nextInt();
            energies[i] = sc.nextInt();
            values[i] = sc.nextInt();
        }

        // dp[t][e] 表示时间上限t，能量上限e时的最大价值
        int[][] dp = new int[maxTime + 1][maxEnergy + 1];

        // 遍历每个星球
        for (int i = 0; i < n; i++) {
            // 倒序遍历时间和能量，确保每个物品只用一次
            for (int t = maxTime; t >= times[i]; t--) {
                for (int e = maxEnergy; e >= energies[i]; e--) {
                    dp[t][e] = Math.max(dp[t][e], dp[t - times[i]][e - energies[i]] + values[i]);
                }
            }
        }

        System.out.println(dp[maxTime][maxEnergy]);
    }
}

def main():
    n = int(input())
    max_time, max_energy = map(int, input().split())

    planets = []
    for _ in range(n):
        # time, energy, value
        planets.append(list(map(int, input().split())))

    # dp[t][e] 表示时间上限t，能量上限e时的最大价值
    dp = [[0] * (max_energy + 1) for _ in range(max_time + 1)]

    # 遍历每个星球
    for time, energy, value in planets:
        # 倒序遍历时间和能量，确保每个物品只用一次
        for t in range(max_time, time - 1, -1):
            for e in range(max_energy, energy - 1, -1):
                dp[t][e] = max(dp[t][e], dp[t - time][e - energy] + value)

    print(dp[max_time][max_energy])

if __name__ == "__main__":
    main()

算法及复杂度

算法: 动态规划 (二维 0/1 背包问题)
时间复杂度: $\mathcal{O}(N \cdot M \cdot K)$ ，其中 $N$ 是星球的数量， $M$ 是续航时间上限， $K$ 是能量储备上限。我们需要三层循环来填充 DP 表。
空间复杂度: $\mathcal{O}(M \cdot K)$ ，用于存储 DP 表。