考試政策-----美團筆試題

題目描述

小明同學在參加一場考試，考試時間2個小時。試卷上一共有n道題目，小明要在規定時間内，完成一定數量的題目。  考試中不限制試題作答順序，對于 i 第道題目，小明有三種不同的政策可以選擇:  (1)直接跳過這道題目，不花費時間，本題得0分。

(2)隻做一部分題目，花費pi分鐘的時間，本題可以得到ai分。  (3)做完整個題目，花費qi分鐘的時間，本題可以得到bi分。 

小明想知道，他最多能得到多少分。

輸入描述:

第一行輸入一個n數表示題目的數量。

接下來n行，每行四個數p_i，a_i，q_i，b_i。(1≤n≤100，1≤p_i≤q_i≤120，0≤a_i≤b_i≤1000
)。      

輸出描述:

輸出一個數，小明的最高得分。      

示例1

輸入

複制

4
20 20 100 60
50 30 80 55
100 60 110 88
5 3 10 6      

輸出

複制

94      

解題思路:

01背包模闆

AC代碼:

package Test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 考試政策 {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[] p=new int[n];
        int[] a=new int[n];
        int[] q=new int[n];
        int[] b=new int[n];
        int[] dp=new int[123];
        for(int i=0;i<n;i++){
            String str=br.readLine();
            p[i]=Integer.parseInt(str.split(" ")[0]);
            a[i]=Integer.parseInt(str.split(" ")[1]);
            q[i]=Integer.parseInt(str.split(" ")[2]);
            b[i]=Integer.parseInt(str.split(" ")[3]);
        }
        for(int i=0;i<n;i++){
            for(int j=120;j>=0;j--){
                if(j>=p[i])dp[j]=Math.max(dp[j],dp[j-p[i]]+a[i]);
                if(j>=q[i])dp[j]=Math.max(dp[j],dp[j-q[i]]+b[i]);
            }
        }
        System.out.println(dp[120]);
    }
}