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 小时内的最大报酬。如果做,那么需要先腾出这个工作所需的时间,然后加上这个工作的报酬。
算法的主要步骤如下:
- 初始化 dp 数组,所有元素设为 0。
- 遍历每个工作。
- 对于每个工作,遍历从该工作所需时间到总时间 T 的每个时间点。
- 对于每个时间点,计算做这个工作和不做这个工作两种情况下的最大报酬,取较大值。
- 最终答案就是 。
在实际实现中,可以使用滚动数组来优化空间复杂度到 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;
}
#OD##OD机考#OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记