蓝桥杯java2020b组第四题分配口罩

问题描述
某市市长获得了若干批口罩，每一批口罩的数目如下：（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 mask.txt，内容与下面的文本相同）
9090400
8499400
5926800
8547000
4958200
4422600
5751200
4175600
6309600
5865200
6604400
4635000
10663400
8087200
4554000

现在市长要把口罩分配给市内的 2 所医院。由于物流限制，每一批口罩只能全部分配给其中一家医院。市长希望 2 所医院获得的口罩总数之差越小越好。请你计算这个差最小是多少？
答案提交
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
 

两家医院得到的口罩总和为sum，另mid = sum/2，各家医院的为sum1，sum2，若sum1不等于sum2，则两家口罩差值为2*(mid - sum1)。

问题则转化为背包问题，背包总的空间为mid，则要从15批口罩中取出i批，使总和sum1最接近mid，答案则为2*(mid - sum1)。

public class disMask {
    public static void main(String[] args) {
        int sum = 0,mid = 0;
        int[] nums = {0, 9090400, 8499400, 5926800, 8547000, 4958200,
                4422600, 5751200, 4175600, 6309600, 5865200, 6604400, 4635000,
                10663400, 8087200, 4554000};
        for (int num:nums){
            sum += num;
        } 
        mid = sum/2;
        int[] dp = new int[mid+1];
        for (int i = 0; i < 16; i++) {
            for (int j = mid;j>=nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]] + nums[i]);
            }
        }
        System.out.println(dp[mid]);
    }
}