一、相关概念

二、题目

题目

思路

背包问题

代码

import java.util.Scanner;

public class 任务执行 {
    
    public static void main(String[] args) {
        new 任务执行().exe();
    }
    
    private void exe(){
        Scanner scan=new Scanner(System.in);
        // 任务个数
        int N=scan.nextInt();
        // 背包容量
        int T=scan.nextInt();
        // 完成任务最小时间
        int[] A=new int[N+1];
        // 完成任务最大时间
        int[] B=new int[N+1];
        for(int i=1;i<=N;i++){
            A[i]=scan.nextInt();
            B[i]=scan.nextInt();
        }
        int r=process(A,B,N,T);
        System.out.println(r);
    }

    /**
     * 
     * @param A：最小时间
     * @param B：最大时间
     * @param N：物品个数
     * @param T：背包容量
     * @return
     */
    private int process(int[] A, int[] B, int N, int T) {
        int[][] f=new int[N+1][T+1];
        for(int i=1;i<=N;i++){
            for(int j=1;j<=T;j++){
                if(j<A[i]){
                    // 最大最小都放不下
                    f[i][j]=f[i-1][j];// 在有限的空间把前i-1件物品放好就行了
                }else if(A[i]<= j && j<B[i]){
                    // 只能放下最下，放不下最大
                    // 不放或放
                    f[i][j]=Math.max(f[i-1][j], f[i-1][j-A[i]]+A[i]);
                }else{
                    // j>=B[i]：可放下最大的
                    // 假设放最小的
                    int min=Math.max(f[i-1][j], f[i-1][j-A[i]]+A[i]);
                    int max=Math.max(f[i-1][j],  f[i-1][j-B[i]]+B[i]);
                    f[i][j]=Math.max(min, max);
                }
            }
        }
        for(int i=1;i<=N;i++){
            for(int j=1;j<=T;j++){
                System.out.print(f[i][j]+"\t");
            }
            System.out.println();
        }
        return f[N][T];
    }

}

参考文献

import java.util.Scanner;

/**
 * Created by zfr on 2018/09/11.
 */
public class 百度 {
    public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int T =scanner.nextInt();
        int[][] nums = new int[N][2];
        for(int i = 0 ;i<N;i++){
            nums[i][0] = scanner.nextInt();
            nums[i][1] = scanner.nextInt();
        }
        int[][] res = new int[N+1][T+1];
        int max = 0;
        for(int i = 1 ; i < N ; i++){
            for(int j = 1 ; j <= T;j++){
                //分情况讨论
                if(nums[i][0] > j){//容量不够，不放
                    res[i][j] = res[i-1][j];
                }else if(nums[i][1] > j){//选择放Ai或者最大值
                    res[i][j] = Math.max(res[i-1][j] , res[i-1][j - nums[i][0]] + nums[i][0]);
                }else {//选择放Bi或者最大值
                    res[i][j] = Math.max(res[i-1][j] , res[i-1][j - nums[i][1]] + nums[i][1]);
                }
                max = Math.max(max,res[i][j]);
            }
        }
        System.out.println(max);
    }
}