数组划分使元素总和最接近

0划分 - 蓝桥云课

将一个数组划分为两个元素总和最接近的两个数组

要使得两组权值的乘积最大，根据数学原理，当两组权值越接近时，它们的乘积就越大。因此，可以将这个问题转化为一个 0 - 1 背包问题，把所有数的总和的一半当作背包的容量，通过动态规划的方法来找出最接近这个容量的一组数的和，进而确定另一组数的和，最终计算出两组权值的乘积

此处使用滚动数组

public class Main {public static void main(String[] args) {int[] nums=new int[]{5160,9191,6410,4657,7492,1531,8854,1253,4520,9231,1266,4801,3484,4323,5070,1789, 2744, 5959, 9426, 4433,4404, 5291 ,2470 ,8533, 7608 ,2935 ,8922 ,5273 ,8364 ,8819, 7374, 8077 ,5336 ,8495 ,5602, 6553, 3548, 5267, 9150 ,3309};long sum=0;for(int i:nums){sum+=i;}long target=sum/2;int[] dp=new int[(int) (target+1)];for (int i = 0; i <nums.length; i++) {for (int j = (int) target; j>=nums[i]; j--){dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}long ans=(sum-dp[(int) target])*dp[(int) target];System.out.println(ans);}
}