40 3
20 10
20 20
20 5
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

30
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

# 输入最大时间限制 T 和任务数 n
T, n = map(int, input().split())

# 输入每个任务的耗时 t 和权重 w
jobs = [tuple(map(int, input().split())) for _ in range(n)]

# 初始化 DP 数组，dp[j] 表示时间限制为 j 时的最大权重
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)

# 输出在时间限制 T 内的最大权重
print(dp[T])

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19

java解法

• 解题思路
• 这是一道经典的0-1 背包问题，需要在给定时间限制
  𝑇
  T 内选择一些任务，最大化总奖励。

问题分析：

有
𝑛
n 个任务，每个任务有耗时
𝑡
𝑖
𝑚
𝑒
𝑠
[
𝑖
]
times[i] 和奖励
𝑟
𝑒
𝑤
𝑎
𝑟
𝑑
𝑠
[
𝑖
]
rewards[i]。
总时间限制为
𝑇
T，要求在时间不超过
𝑇
T 的情况下，选择任务使得总奖励最大。
解决方法：

使用动态规划（DP）解决。
定义 dp[j] 表示在时间限制为
𝑗
j 时可以获得的最大奖励。
遍历每个任务，根据其耗时和奖励，更新当前时间限制内的最大奖励。
动态规划公式：

初始状态：dp[0] = 0，即在时间限制为 0 时，奖励为 0。
转移方程：dp[j] = max(dp[j], dp[j - time] + reward)，表示是否选择当前任务。
倒序遍历时间
𝑇
T 至
𝑡
𝑖
𝑚
𝑒
time，确保每个任务只被选择一次

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入时间限制 T 和任务数 n
        int T = sc.nextInt();
        int n = sc.nextInt();

        // 初始化任务耗时和奖励数组
        int[] times = new int[n];
        int[] rewards = new int[n];

        // 输入每个任务的耗时和奖励
        for (int i = 0; i < n; i++) {
            times[i] = sc.nextInt();
            rewards[i] = sc.nextInt();
        }

        // 输出最大奖励
        System.out.println(maxReward(T, n, times, rewards));
    }

    // 计算最大奖励的函数
    public static int maxReward(int T, int n, int[] times, int[] rewards) {
        // 初始化 DP 数组，dp[j] 表示时间限制为 j 时的最大奖励
        int[] dp = new int[T + 1];

        // 遍历每个任务
        for (int i = 0; i < n; i++) {
            int time = times[i];   // 当前任务的耗时
            int reward = rewards[i]; // 当前任务的奖励

            // 倒序遍历时间限制，确保每个任务只被选择一次
            for (int j = T; j >= time; j--) {
                // 更新时间限制 j 内的最大奖励
                dp[j] = Math.max(dp[j], dp[j - time] + reward);
            }
        }

        // 返回时间限制为 T 时的最大奖励
        return dp[T];
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">