E卷-最大报酬(100分)

最大报酬

问题描述

小明每周上班都会拿到自己的工作清单，工作清单内包含 项工作，每项工作都有对应的耗时时间（单位 h）和报酬，工作的总报酬为所有已完成工作的报酬之和。请你帮小明安排工作，保证小明在指定的工作时间内工作收入最大化。

输入格式

第一行包含两个正整数 和 。 代表工作时长（单位 h）， 代表工作数量。 接下来 行，每行包含两个整数 和 。 代表第 项工作消耗的时长（单位 h）， 代表第 项工作的报酬。

输出格式

输出一个整数，表示小明在指定工作时长内可获得的最大报酬。

样例输入

40 3
20 10
20 20
20 5

样例输出

30

样例解释

无

数据范围

• 
• 
• 
• 为整数

题解

这道题目本质上是一个 0-1 背包问题。每项工作可以看作是一个物品，工作时长就是物品的重量，报酬就是物品的价值。我们需要在有限的时间（背包容量）内，选择一些工作（物品）来获得最大的报酬（价值）。

解决这个问题的关键在于使用动态规划。定义一个二维数组 dp[i][j]，表示前 i 个工作在 j 小时内能获得的最大报酬。状态转移方程如下：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i]] + w[i])  if j >= t[i]
dp[i][j] = dp[i-1][j]                               if j < t[i]

这个方程的含义是：对于第 i 个工作，有两种选择：做或不做。如果不做，那么最大报酬就是前 i-1 个工作在 j 小时内的最大报酬。如果做，那么需要先腾出这个工作所需的时间，然后加上这个工作的报酬。

算法的主要步骤如下：

1. 初始化 dp 数组，所有元素设为 0。
2. 遍历每个工作。
3. 对于每个工作，遍历从该工作所需时间到总时间 T 的每个时间点。
4. 对于每个时间点，计算做这个工作和不做这个工作两种情况下的最大报酬，取较大值。
5. 最终答案就是 。

在实际实现中，可以使用滚动数组来优化空间复杂度到 O(T)。这种优化不会改变时间复杂度，但可以大大减少内存使用。

参考代码

• Python

# 读取输入
T, n = map(int, input().split())
jobs = [list(map(int, input().split())) for _ in range(n)]

# 初始化dp数组
dp = [0] * (T + 1)

# 动态规划过程
for t, w in jobs:
    for j in range(T, t - 1, -1):
        # 状态转移：选择当前工作或不选择
        dp[j] = max(dp[j], dp[j - t] + w)

# 输出结果
print(dp[T])

• C

#include <stdio.h>
#include <string.h>

#define MAX_T 1000000
#define MAX_N 3000

int main() {
    int T, n;
    int t[MAX_N], w[MAX_N];
    int dp[MAX_T + 1];

    // 读取输入
    scanf("%d %d", &T, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &t[i], &w[i]);
    }

    // 初始化dp数组
    memset(dp, 0, sizeof(dp));

    // 动态规划过程
    for (int i = 0; i < n; i++) {
        for (int j = T; j >= t[i]; j--) {
            // 状态转移：选择当前工作或不选择
            if (dp[j] < dp[j - t[i]] + w[i]) {
                dp[j] = dp[j - t[i]] + w[i];
            }
        }
    }

    // 输出结果
    printf("%d\n", dp[T]);

    return 0;
}

• Javascript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];
rl.on('line', (line) => {
    lines.push(line);
});

rl.on('close', () => {
    const [T, n] = lines[0].split(' ').map(Number);
    const jobs = lines.slice(1).map(line => line.split(' ').map(Number));

    // 初始化dp数组
    let dp = new Array(T + 1).fill(0);

    // 动态规划过程
    for (let [t, w] of jobs) {
        for (let j = T; j >= t; j--) {
            // 状态转移：选择当前工作或不选择
            dp[j] = Math.max(dp[j], dp[j - t] + w);
        }
    }

    // 输出结果
    console.log(dp[T]);
});

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        int T = scanner.nextInt();
        int n = scanner.nextInt();
        int[] t = new int[n];
        int[] w = new int[n];
        
        for (int i = 0; i < n; i++) {
            t[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        
        // 初始化dp数组
        int[] dp = new int[T + 1];
        
        // 动态规划过程
        for (int i = 0; i < n; i++) {
            for (int j = T; j >= t[i]; j--) {
                // 状态转移：选择当前工作或不选择
                dp[j] = Math.max(dp[j], dp[j - t[i]] + w[i]);
            }
        }
        
        // 输出结果
        System.out.println(dp[T]);
        
        scanner.close();
    }
}

• Cpp

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

using namespace std;

int main() {
    int T, n;
    cin >> T >> n;
    
    vector<int> t(n), w(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> w[i];
    }
    
    // 初始化dp数组
    vector<int> dp(T + 1, 0);
    
    // 动态规划过程
    for (int i = 0; i < n; i++) {
        for (int j = T; j >= t[i]; j--) {
            // 状态转移：选择当前工作或不选择
            dp[j] = max(dp[j], dp[j - t[i]] + w[i]);
        }
    }
    
    // 输出结果
    cout << dp[T] << endl;
    
    return 0;
}