2019春招，完美世界笔试第一题

￡神魔★判官ぃ 2022-02-19 11:57 248阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JleF9XVVNU_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JleF9XVVNU_size_16_color_FFFFFF_t_70 1][]

### 我的解答： ###

import java.util.*;
    
    public class Main {
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		while (sc.hasNext()) {
    
    			/*1.读取数据*/
    			int n = sc.nextInt();// 题目的数量
    
    			// 注意：我们声明数组的长度为"n+1",并另score[0]和time[0]等于0;
    			// 从而使得 数组的下标，对应于题目的序号。即score[1]对应于第一题的分数,time[1]对应于第一题的时间
    			int[] score = new int[n + 1]; // {0,5,4,3,5,2} 每道题对应的得分
    			int[] time = new int[n + 1]; // {0,2,2,3,5,1} 每道题要花的时间
    
    			score[0] = 0;
    			for (int i = 1; i < n + 1; i++) {
    				score[i] = sc.nextInt();
    			}
    
    			time[0] = 0;
    			for (int i = 1; i < n + 1; i++) {
    				time[i] = sc.nextInt();
    			}
    
    			int limitTime = sc.nextInt();
    
    			/*2.开始求解。相当于用动态规划法求解01背包问题*/
    			int[][] v = new int[n + 1][limitTime + 1];// 动态规划表.使得v[i][j]对应于：有i个题目可选做，在j时间内，我们可能得到的最高分
    
    			// 填动态规划表
    			for (int i = 0; i < n + 1; i++) {
    				for (int j = 0; j < limitTime + 1; j++) {
    					if (i == 0) {
    						v[i][j] = 0; // 边界情况：若只有0道题目可以选做，那只能得到0分。令V(0,j)=0
    					} else if (j == 0) {
    						v[i][j] = 0; // 边界情况：若只有0分钟的考试时间，那也只能得0分。令V(i,0)=0
    					} else {
    						if (j < time[i]) {
    							v[i][j] = v[i - 1][j];
    						} else {
    							v[i][j] = Math.max(v[i - 1][j], v[i - 1][j - time[i]] + score[i]);
    						}
    					}
    				}
    			}
    
    			System.out.println(v[n][limitTime]);// 有n个题目可选做，在limitTime考试时间内，我们可能得到的最高分
    
    		}
    
    	}
    
    }

### 测试结果： ###

> 输入：
> 
> 5  
> 5 4 3 5 2  
> 2 2 3 5 1  
> 10
> 
> 输出：  
> 16
> 
> \----------------------------------------------------
> 
> 输入：  
> 4  
> 3 4 5 6  
> 2 3 4 5  
> 8
> 
> 输出：  
> 10

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JleF9XVVNU_size_16_color_FFFFFF_t_70]: /images/20220219/955830ef31f7474b82ae632a37a41fe3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JleF9XVVNU_size_16_color_FFFFFF_t_70 1]: /images/20220219/1a2ee152152344f8a6b76ae5988138cd.png