华为OD机试 - 执行任务赚积分 - 动态规划（Java 2024 C卷 100分）

青旅半醒 2024-05-06 09:58 80阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

现有 N 个任务需要处理，同一时间只能处理一个任务，处理每个任务所需要的时间固定为 1。

每个任务都有最晚处理时间限制和积分值，在最晚处理时间点之前处理完成任务才可获得对应的积分奖励。

可用于处理任务的时间有限，请问在有限的时间内，可获得的最多积分。

### 二、输入描述 ###

第一行为一个数 N ，表示有 N 个任务（1 ≤ N ≤ 100 ）

第二行为一个数 T ，表示可用于处理任务的时间。（1 ≤ T ≤ 100）

接下来 N 行，每行两个空格分隔的整数（SLA 和 和 V ），SLA 表示任务的最晚处理时间，V 表示任务对应的积分。

1≤SLA≤100 , 0 ≤ V ≤ 100000

### 三、输出描述 ###

可获得的最多积分。

#### 1、输入 ####

4  
3  
1 2  
1 3  
1 4  
1 5

#### 2、输出 ####

#### 3、说明 ####

虽然有 3 个单位的时间用于处理任务，可是所有任务在时刻1之后都无效。 所以在第 1 个时间单位内，选择处理有 5 个积分的任务。1−3 时无任务处理。

### 四、解题思路 ###

本题的本质是一个类似于背包问题的动态规划问题，称为"01背包问题"。在这种问题中，我们需要决定在给定的总时间 T 内，应该完成哪些任务以最大化积分。每个任务都可以视为一个物品，任务的处理时间为其"重量"（在此题中恒为1），任务的积分值为其"价值"。

#### 解题思路 ####

1.  定义动态规划数组：dp\[i\]\[t\] 表示在前 i 个任务中，使用时间 t 所能获得的最大积分。
2.  状态转移：对于每个任务，有两种选择：
3.  不处理这个任务：此时积分为 dp\[i-1\]\[t\]。
4.  处理这个任务（前提是我们有足够的时间处理这个任务且在它的最晚处理时间之前）：积分为 dp\[i-1\]\[t-1\] + V\[i\]。
5.  边界条件：dp\[0\]\[t\] = 0 对所有 t，即没有任务可处理时积分为0。
6.  优化存储：可以使用一维数组滚动更新来减少空间复杂度。

### 五、Java算法源码 ###

public class OdTest01 {
        
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();  // 读取任务数量
            int T = scanner.nextInt();  // 可用时间
    
            // 读取每个任务的最晚处理时间和积分值
            int[] SLA = new int[N + 1];
            int[] V = new int[N + 1];
            for (int i = 1; i <= N; i++) {
        
                SLA[i] = scanner.nextInt();
                V[i] = scanner.nextInt();
            }
    
            // dp[t] 表示在时间 t 内能获得的最大积分
            int[] dp = new int[T + 1];
    
            // 动态规划处理
            for (int i = 1; i <= N; i++) {
        
                // 从后向前更新，以避免一维数组中的值被提前覆盖
                for (int t = T; t >= 1; t--) {
        
                    if (t <= SLA[i]) {
          // 只有在允许的时间内处理任务时才考虑
                        dp[t] = Math.max(dp[t], dp[t - 1] + V[i]);
                    }
                }
            }
    
            // 查找可用时间内能获得的最大积分
            int maxScore = 0;
            for (int t = 1; t <= T; t++) {
        
                maxScore = Math.max(maxScore, dp[t]);
            }
    
            // 输出结果
            System.out.println(maxScore);
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

4  
3  
1 2  
1 3  
1 4  
3 5

#### 2、输出 ####

#### 3、说明 ####

第 1 个时间单位内，处理任务3，获得 4 个积分  
第 2 个时间单位内，处理任务 4，获得 5 个积分  
第 3 个时间单位内，无任务可处理。  
共获得 9 个积分

![在这里插入图片描述][b24da9c21c8d4c6e9cf026054a2b8879.png_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/9c3da2ff625c4cd6ade05d9768a24a58.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[b24da9c21c8d4c6e9cf026054a2b8879.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/ed9978c27ed64908a425f1a48e7b6658.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/06/b5685e5ece7f428baaf2863299b890dc.gif