问题描述:
某市市长获得了若干批口罩,给定每批口罩的数量,
市长要把口罩分配给市内的 2 所医院,由于物流限制,每一批口罩只能全部分配给其中一家医院。
市长希望 2 所医院获得的口罩总数之差越小越好。 请你计算这个差最小是多少?
答案提交
这是一道结果填空题,你只需要算出结果后提交即可。
本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
解题思路:
> 本题是一个典型的递归问题(多路径问题) > dfs函数的三个参数分别为 k、sum1、sum2 > k代表正在处理数字的下标 > sum1为1号医院的口罩数量 > sum2位2号医院的口罩数量 > 当k=15时,说明所有口罩全部分配完成,此时要确定最小值和当前两个医院数量的差值 > 函数体中处理的是不同路径 > 第一个是给1号医院分配 > 第二个是给2号医院分配 > 经过多次递归回溯,会计算出所有分配情况的最小值
代码:
public class Main { public static long res=Long.MAX_VALUE; public static long num[]={9090400, 8499400, 5926800, 8547000, 4958200, 4422600, 5751200, 4175600, 6309600, 5865200, 6604400, 4635000, 10663400, 8087200, 4554000 }; public static void main(String[] args){ dfs(0, 0, 0); System.out.println(res); } public static void dfs(int k,long sum1,long sum2 ) { if(k==15) { res=res<Math.abs(sum1-sum2)?res:Math.abs(sum1-sum2); return; } dfs(k+1, sum1+num[k], sum2); dfs(k+1, sum1, sum2+num[k]); } }
答案:
2400