考试策略

[编程题]考试策略

热度指数：5016 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小明同学在参加一场考试，考试时间 2 个小时。试卷上一共有 n 道题目，小明要在规定时间内，完成一定数量的题目。考试中不限制试题作答顺序，对于 i 第道题目，小明有三种不同的策略可以选择:

(1)直接跳过这道题目，不花费时间，本题得0分。

(2)只做一部分题目，花费 pi 分钟的时间，本题可以得到 ai 分。

(3)做完整个题目，花费 qi 分钟的时间，本题可以得到 bi 分。

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

数据范围： $1 \le n \le 100 \$ ， $1 \le p_i,q_i \le 120 \$ ， $0 \le a_i \le b_i \le 1000 \$

输入描述:

第一行输入一个n数表示题目的数量。

接下来n行，每行四个数p_i，a_i，q_i，b_i。

输出描述:

输出一个数，小明的最高得分。

示例1

输入

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

输出

算法知识视频讲解

Java

May_HanaJung

public class Main{

public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int total = sc.nextInt();
int[] weight = new int[2* total];
int[] value = new int[2 * total];
int index = 0;
sc.nextLine();
for (int i = 0; i < total; i++) {

String[] s = sc.nextLine().split(" ");
weight[index] = Integer.parseInt(s[0]);
value[index] = Integer.parseInt(s[1]);
index += 1;
weight[index] = Integer.parseInt(s[2]);
value[index] = Integer.parseInt(s[3]);
index ++;
}

int maxScore = computeScore(120,weight, value);
System.out.println(maxScore);
}

private static int computeScore(int maxSize,int[] weight,int[] value){
int[] dp = new int[maxSize + 1];

for(int i = 0;i<weight.length;i++){
for(int j = maxSize; j>= weight[i];j--){
dp[j] = Math.max(dp[j-weight[i]]+value[i],dp[j]);
}
}

return dp[maxSize];
}
}

发表于 2021-08-06 21:38:22 回复(0)

Java

柳上原

import java.util.Scanner;

// 考试策略
public class Main {
    /**
     * dp[i][j]   // i门课程用j分钟时的最高得分
     *
     *
     *
     * @param n
     * @param pi
     * @param ai
     * @param qi
     * @param bi
     * @return
     */
    public static int solve(int n, int[] pi, int[] ai, int[] qi, int[] bi){
        int[][] dp = new int[n + 1][121];
        dp[0][0] = 0;
        for (int i=1;i<=n;i++){
            dp[i][0] = 0;
        }

        for (int i=1;i<=120;i++){
            dp[0][i] = 0;
        }

        for (int i=1;i<=n;i++){
            for (int j=1;j<=120;j++){
                int a = dp[i-1][j];
                int b = 0;
                if (j - pi[i-1] >= 0){
                    b = dp[i-1][j-pi[i-1]] + ai[i-1];
                }
                int c = 0;
                if (j - qi[i-1] >= 0){
                    c = dp[i-1][j-qi[i-1]] + bi[i-1];
                }
                dp[i][j] = Math.max(a, Math.max(b, c));
            }
        }

        return dp[n][120];
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] pi = new int[n];
        int[] ai = new int[n];
        int[] qi = new int[n];
        int[] bi = new int[n];
        for (int i=0; i<n; i++){
            pi[i] = scanner.nextInt();
            ai[i] = scanner.nextInt();
            qi[i] = scanner.nextInt();
            bi[i] = scanner.nextInt();
        }


        System.out.println(solve(n, pi, ai, qi, bi));
    }
}

动态规划, 注意输入的意思, 每行分别为pi、ai、qi、bi; 一开始还以为每行依次是p、a、q、b

编辑于 2020-03-18 12:48:54 回复(0)

Java

LHC0512

Java解法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n= Integer.parseInt(scanner.nextLine());
        int[][] record = new int[n][4];
        //接下来n行，每行四个数p_i，a_i，q_i，b_i
        for (int i = 0; i < n; i++) {
            String[] s = scanner.nextLine().split(" ");
            for (int j = 0; j < 4; j++) {
                record[i][j]=Integer.parseInt(s[j]);
            }
        }
        int[] dp=new int[121];
        for(int i = 0; i < n; i++)
            for(int j = 120; j >= 0; j--) {
                if(record[i][0] <= j) dp[j] = Math.max(dp[j], dp[j-record[i][0]] + record[i][1]);
                if(record[i][2] <= j) dp[j] = Math.max(dp[j], dp[j-record[i][2]] + record[i][3]);
            }
        System.out.println(dp[120]);
    }
}

发表于 2020-03-01 21:59:36 回复(1)