【Java每日一题，01背包问题】 kkksc03考前临时抱佛脚

Introduction

Input

Output

输出一行,为复习完毕最短时间。

Sample

input

1 2 1 3		
5
4 3
6
2 4 3

output

20

Solution

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

/**
 * @author liangyuanshao
 * @date 2022/5/14 - 18:01
 */
public class Main {

  public static void main(String[] args) {
    Scanner s=new Scanner(System.in);
    int[] arr=new int[4];
    int time=0;
    for(int i=0;i<4;i++){
      arr[i]=s.nextInt();
    }
    for(int k=0;k<4;k++){
      int n=arr[k];
      int[] sub=new int[n+1];
      int sum=0;
      for(int i=1;i<=n;i++){
        sub[i]=s.nextInt();
        sum+=sub[i];
      }
      Arrays.sort(sub);
      int[][] bag=new int[n+1][sum/2+1];
      for (int i=1;i<=n;i++){
        for (int j=1;j<=sum/2;j++){
          bag[i][j]=bag[i-1][j];
          if(j>=sub[i]){
            bag[i][j]=Math.max(bag[i][j],bag[i-1][j-sub[i]]+sub[i]);
          }
        }
      }
      time+=(sum-bag[n][sum/2]);
    }
    System.out.println(time);


  }
}

Experience

这题目难度在于根本想不到是01背包问题，刚开始是考考虑问题使用的是贪心，题目给的例子过了，但是测试样例全错。看了题解发现考虑问题的方式很重要，一个科目的全部时间能求出来，其实就是一半脑子的时间最接近总时间的一般就行了。相当于固定空间放最大的价值。
其实样例不大，全搜索也行。