牛客网真题-77-考试策略

0-1背包问题

package org.niuke.solution77;

import java.io.*;

public class Main {
    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 + 1];
        int[] a = new int[n + 1];
        int[] q = new int[n + 1];
        int[] b = new int[n + 1];
        for(int i = 1; i <= n; i++){
            String[] line = br.readLine().split(" ");
            p[i] = Integer.parseInt(line[0]);
            a[i] = Integer.parseInt(line[1]);
            q[i] = Integer.parseInt(line[2]);
            b[i] = Integer.parseInt(line[3]);
        }

        //        int[][] dp=new int[n+1][121];
        //        for(int i=1;i<=n;i++){
        //            for(int j=0;j<=120;j++){
        //                dp[i][j]=dp[i-1][j];
        //                if(j>=p[i]) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-p[i]]+a[i]);
        //                if(j>=q[i]) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-q[i]]+b[i]);
        //            }
        //        }
        //        System.out.println(dp[n][120]);

        int[] dp = new int[121];
        for(int i = 1; i <= n; i++){
            for(int j = dp.length - 1; 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]);
    }
}