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

1 2 1 3   
5
4 3
6
2 4 3

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);
  }
}