刷题笔记合集🔗

最大报酬

问题描述

小明每周上班都会拿到自己的工作清单，工作清单内包含 项工作，每项工作都有对应的耗时时间（单位 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 (i