题面描述

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

思路

本题是一个典型的0-1 背包问题。我们需要在总耗时不超过 $T$ 的情况下，选择若干工作使得总报酬最大化。

关键点分析：

1. 状态定义：设 $dp[j]$ 表示在总耗时不超过 $j$ 小时的情况下，能够获得的最大报酬。
2. 状态转移：对于每一项工作 $(t_i, w_i)$，我们可以选择是否完成这项工作。
   • 如果选择完成，则有 $dp[j] = \max(dp[j], dp[j - t_i] + w_i)$。
   • 如果不选择，则保持原来的 $dp[j]$ 不变。
3. 初始化：$dp[0] = 0$，表示在耗时为0的情况下，报酬为0。其他 $dp[j]$ 可以初始化为0。
4. 遍历顺序：为了避免重复计算，我们需要从后向前遍历时间 $j$，确保每项工作只被选择一次。

代码分析

1. 输入处理：

   • 使用 ios::sync_with_stdio(false); 和 cin.tie(0); 来加快输入速度，适用于大规模数据。
   • 读取总工作时长 $T$ 和工作数量 $n$。
   • 使用一个 vector 存储所有工作的耗时和报酬。

2. 动态规划数组初始化：

   • 创建一个大小为 $T+1$ 的数组 dp，初始化所有元素为0，表示在不同耗时下的最大报酬。

3. 动态规划状态转移：

   • 对于每一项工作 $(t, w)$，从总耗时 $T$ 开始向下遍历到 $t$，更新 dp[j]。
   • 更新规则：dp[j] = max(dp[j], dp[j - t] + w)，即选择是否完成当前工作以获得更高的报酬。

4. 结果计算：

   • 遍历 dp 数组，找到最大的报酬值即为最终答案。

5. 时间优化：

   • 使用一维数组进行状态压缩，减少内存占用。
   • 通过从后向前遍历，确保每项工作只被选择一次，避免重复计算。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T, n;
    cin >> T >> n;
    vector<pair<int, int>> jobs(n);
    for(int i=0;i<n;i++) cin >> jobs[i].first >> jobs[i].second;
    // Initialize DP array
    vector<int> dp(T+1, 0);
    for(int i=0;i<n;i++){
        int t = jobs[i].first;
        int w = jobs[i].second;
        // Iterate from T downto t
        for(int j = T; j >= t; j--){
            if(dp[j - t] + w > dp[j]){
                dp[j] = dp[j - t] + w;
            }
        }
    }
    // Find the maximum reward
    int max_reward = 0;
    for(int j=0; j<=T; j++) max_reward = max(max_reward, dp[j]);
    cout << max_reward;
}

python

import sys

def main():
    import sys
    import sys
    # 读取输入
    T, n = map(int, sys.stdin.readline().split())
    jobs = []
    for _ in range(n):
        t, w = map(int, sys.stdin.readline().split())
        jobs.append((t, w))
    
    # 初始化DP数组
    dp = [0] * (T + 1)
    
    for t, w in jobs:
        # 从T倒序遍历到t，确保每项工作只被选择一次
        for j in range(T, t - 1, -1):
            if dp[j - t] + w > dp[j]:
                dp[j] = dp[j - t] + w
    
    # 找到最大的报酬
    max_reward = max(dp)
    print(max_reward)

if __name__ == "__main__":
    main()

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int T = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        
        int[] t = new int[n];
        int[] w = new int[n];
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            t[i] = Integer.parseInt(st.nextToken());
            w[i] = Integer.parseInt(st.nextToken());
        }
        
        // 初始化DP数组
        int[] dp = new int[T + 1];
        
        for (int i = 0; i < n; i++) {
            // 从T倒序遍历到t[i]，确保每项工作只被选择一次
            for (int j = T; j >= t[i]; j--) {
                if (dp[j - t[i]] + w[i] > dp[j]) {
                    dp[j] = dp[j - t[i]] + w[i];
                }
            }
        }
        
        // 找到最大的报酬
        int maxReward = 0;
        for (int j = 0; j <= T; j++) {
            if (dp[j] > maxReward) {
                maxReward = dp[j];
            }
        }
        
        System.out.println(maxReward);
    }
}

题目内容

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

输入描述

输入的第一行为两个正整数 $T$，$n$。

• $T$ 代表工作时长（单位 $h$， $0 < T < 1000$），
• $n$ 代表工作数量（ $1 < n ≤ 3000$）。

接下来是 $n$ 行，每行包含两个整数 $t$，$w$。

• $t$ 代表该工作消耗的时长（单位 $h$， $t > 0$），$w$ 代表该项工作的报酬。

输出描述

输出小红指定工作时长内工作可获得的最大报酬。

样例1

输入

40 3
20 10
20 20
20 5

输出

30

说明