星际勘探任务

题意

有 颗未探索的星球，飞船拥有 单位续航时间和 单位能量储备。探索第 颗星球需要 时间、 能量，能获得 科研数据价值。每颗星球最多探索一次，在总时间不超过 、总能量不超过 的前提下，求最大科研数据价值。

思路

看到这题，有没有觉得很熟悉？对，就是经典的 0/1 背包——只不过背包从一维变成了二维，同时受到时间和能量两个容量限制。

怎么从一维背包推广？

回忆一下标准的一维 0/1 背包：定义 表示容量为 时的最大价值，逆序枚举 来保证每件物品只选一次。

现在多了一个维度，怎么办？直接加一维就好：

$$

对于每颗星球 ，转移方程是：

$$

和一维背包一样，两个维度都要逆序枚举，这样才能保证每颗星球只被选一次。

为什么两维都要逆序？

关键在于：更新 时用到的 必须是"还没考虑第 颗星球"的旧值。如果正序枚举 或 ，就可能用到已经包含第 颗星球的值，导致同一颗星球被重复选取。

复杂度

  • 时间：
  • 空间：

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int T,E;
    scanf("%d%d",&T,&E);
    vector<int> ti(n),ei(n),vi(n);
    for(int i=0;i<n;i++) scanf("%d%d%d",&ti[i],&ei[i],&vi[i]);
    vector<vector<int>> dp(T+1, vector<int>(E+1, 0));
    for(int i=0;i<n;i++){
        for(int j=T;j>=ti[i];j--){
            for(int k=E;k>=ei[i];k--){
                dp[j][k] = max(dp[j][k], dp[j-ti[i]][k-ei[i]] + vi[i]);
            }
        }
    }
    printf("%d\n", dp[T][E]);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int T = sc.nextInt(), E = sc.nextInt();
        int[] ti = new int[n], ei = new int[n], vi = new int[n];
        for (int i = 0; i < n; i++) {
            ti[i] = sc.nextInt();
            ei[i] = sc.nextInt();
            vi[i] = sc.nextInt();
        }
        int[][] dp = new int[T + 1][E + 1];
        for (int i = 0; i < n; i++) {
            for (int j = T; j >= ti[i]; j--) {
                for (int k = E; k >= ei[i]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - ti[i]][k - ei[i]] + vi[i]);
                }
            }
        }
        System.out.println(dp[T][E]);
    }
}

import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    T, E = map(int, input().split())
    items = []
    for _ in range(n):
        t, e, v = map(int, input().split())
        items.append((t, e, v))

    E1 = E + 1
    dp = [[0] * E1 for _ in range(T + 1)]

    for t, e, v in items:
        for j in range(T, t - 1, -1):
            dpj = dp[j]
            dpjt = dp[j - t]
            for k in range(E, e - 1, -1):
                nv = dpjt[k - e] + v
                if nv > dpj[k]:
                    dpj[k] = nv

    sys.stdout.write(str(dp[T][E]) + '\n')

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const [T, E] = lines[1].split(' ').map(Number);
    const items = [];
    for (let i = 0; i < n; i++) {
        const [t, e, v] = lines[2 + i].split(' ').map(Number);
        items.push([t, e, v]);
    }
    const dp = Array.from({length: T + 1}, () => new Int32Array(E + 1));
    for (const [t, e, v] of items) {
        for (let j = T; j >= t; j--) {
            for (let k = E; k >= e; k--) {
                const nv = dp[j - t][k - e] + v;
                if (nv > dp[j][k]) dp[j][k] = nv;
            }
        }
    }
    console.log(dp[T][E]);
});