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