2023华为OD机试真题-工作安排(JAVA、Python、C++)

题目描述：
小明每周上班都会拿到自己的工作清单，工作清单内包含n项工作，每项工作都有对应的耗时时长（单位h）和报酬，工作的总报酬为所有已完成工作的报酬之和。那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。
输入描述：
输入的第一行为两个正整数T，n。T代表工作时长（单位h，0 < T < 100000），n代表工作数量(1 < n ≤ 3000)。
接下来是n行，每行包含两个整数t，w。t代表该项工作消耗的时长（单位h，t > 0），w代表该项工作的报酬。
输出描述：
输出小明指定工作时长内工作可获得的最大报酬。
补充说明：
 收起
示例1
输入：
40 3
20 10
20 20
20 5
输出：
30
 

import java.util.Scanner;
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int n = sc.nextInt();
 
        int res = 0;
        int[] tarr = new int[n];
        int[] warr = new int[n];
        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            int w = sc.nextInt();
            tarr[i] = t;
            warr[i] = w;
        }
 
        //动态规划
        int[][] dp = new int[n + 1][T + 1];
 
        //初始化
        for (int i = 0; i < T + 1; i++) {
            dp[0][i] = 0;
        }
        for (int j = 0; j < n + 1; j++) {
            dp[j][0] = 0;
        }
 
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < T + 1; j++) {
                //如果剩余时间还能干第j个工作
                if (tarr[i - 1] <= j) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - tarr[i - 1]] + warr[i - 1]);
                }
            }
        }
 
        res = dp[n][T];
        System.out.println(res);
    }
}

T, n = map(int, input().split())
Time_pay = []
while True:
    try:
        time, num = map(int, input().split())
        Time_pay.append((time, num))
    except:
        break
time = [i[0] for i in Time_pay]
value = [i[1] for i in Time_pay]
total_time = T
dp = [0] * (total_time + 1)
for i in range(len(time)):
    for j in range(total_time, time[i]-1, -1):
        dp [j] = max(dp[j], dp[j - time[i]] + value[i])
print(dp[-1])

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int T,n;
    cin>>T>>n;
    vector<int> t(n,0);
    vector<int> w(n,0);
    for(int i=0;i<n;i++){
        cin>>t[i]>>w[i];
    }
    vector<vector<int>>dp(n+1,vector<int>(T+1,0));
    for(int i=1;i<n+1;i++){
        for(int j=1;j<T+1;j++){
            dp[i][j]=j>=t[i-1]?max(dp[i-1][j],dp[i-1][j-t[i-1]]+w[i-1]):dp[i-1][j];
        }
    }
    cout<<dp[n][T];
     
}