【华为OD机试题】最大报酬 Java代码实现

Myth丶恋晨 2024-03-23 23:30 103阅读 0赞

##### 题目描述 #####

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

##### 输入 #####

输入的第一行为两个正整数T，n。 T代表工作时长（单位h，0<T<1000000），n代表工作数量（1<n≤3000）。 接下来是n行，每行包含两个整数t，w。 t代表该工作消耗的时长（单位h，t>0）,w代表该项工作的报酬。

##### 输出 #####

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

##### 样例输入 #####

40 3
    20 10
    20 20
    20 5

##### 样例输出 #####

### 我的代码： ###

个人见解！！！！欢迎讨论！！！！！！！！！

import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Scanner;
    import java.util.List;
    public class Main {
        public static void main(String[] args) {
            //输入，初始化
    		Scanner sc = new Scanner(System.in);
    		int time = sc.nextInt();
    		int count = sc.nextInt();
    		int[] ot = new int[count];
    		int[] oc = new int[count];
    		for(int i=0;i<count;i++) {
    			ot[i]=sc.nextInt();
    			oc[i]=sc.nextInt();
    		}
            
            //输出
    		List<Integer> res = new ArrayList<Integer>();
    		dfs(0,40,ot,oc,0,res);
    		Integer max = Collections.max(res);
    		System.out.println(max);
    
    	}
    
    	public static void dfs(int index,int left,int[] ot,int[] oc,int sum,List<Integer> res) {
    		if(index==ot.length) {
    			res.add(sum);
    			return;
    		}
    
    		
    		//不选
    		dfs(index+1,left,ot,oc,sum,res);
    		
    		//选
    		if(left-ot[index]>=0) {
    			sum=sum+oc[index];
    			dfs(index+1,left-ot[index],ot,oc,sum,res);
    		}
    
    	}
    }