將數組分成兩個子數組，以便數組之和的差值最小？

Question

輸入爲[4,13,14,15,16]。輸出應該是[16,15]和[14,13,4]。

其中

1. 我按降序排列
2. 取前兩個元素在兩個列表
3. 現在添加的元素列表中誰和最小的數組進行排序，我能想到以下算法的

---

public class TestMinDiff { 

    public static void main(String[] args) { 
     Integer[] array = {4,13,14,15,16}; 

     Arrays.sort(array, Collections.reverseOrder()); 

     List<Integer> list1 = new ArrayList<Integer>(); 
     List<Integer> list2 = new ArrayList<Integer>(); 

     int list1Sum = 0; 
     int list2Sum = 0; 

     for(int i: array) { 
      if(list1Sum<=list2Sum) { 
       list1Sum = list1Sum + i; 
       list1.add(i); 
      } else { 
       list2Sum = list2Sum + i; 
       list2.add(i); 
      } 
     } 
    } 
} 

輸出爲

1. 列表1爲[16,13,4]。
2. 列表2是[15,14]。

看起來像我的算法需要進一步改進。對我來說，它看起來像是一個NP問題。但是我不能想到這裏給出的輸出爲 [16,15]和[14,13,4]的算法。

Answer 1

這是knapsack problem。在一般情況下它是NP完全的，但對於小整數可以有效解決。

讓我們以[4,13,14,15,16]的示例數組爲例。總數是62.我們把這個變成了揹包問題，我們有這套物品，但揹包容量是62÷2 = 31.如果我們選擇總數不超過31的物品，那麼這解決了你的問題最小化兩個分開的列表之間的差異的問題。

有一個標準的算法來解決揹包問題，我不會在這裏解釋。

Answer 2

我明白你的問題：你想將數組分爲兩個數組，每個數組的總和最小。 你應該比較list1Sum和list2Sum添加i後，所以：

if(list1Sum + i <= list2Sum){ 
      list1Sum= list1Sum +i; 
      list1.add(i); 
     }else{ 
      list2Sum= list2Sum +i; 
      list2.add(i); 
     } 

Answer 3

我同意Nayuki算法。它的一維揹包問題，您可以將所有投入的價值視爲投入（或權重）。

現在找到兩個子陣列，其是之和小於等於31

import java.util.ArrayList; 
import java.util.List; 
public class Knapsack { 

    public static void main(String[] args) { 

     int[] weight = {4,13,14,15}; 
     int[] value = {4,13,14,15}; 
     int targetSum = 31; 

     knapsack(weight, value, targetSum); 

    } 

    public static void knapsack(int[] weight, int[] value, int targetSum) { 

     int[][] weightValMatrix = new int[weight.length + 1][targetSum + 1]; 

     for (int i = 0; i < weight.length; i++) { 
      for (int k = 0; k < targetSum + 1; k++) { 
       weightValMatrix[i][k] = 0; 
      } 

     } 

     for (int i = 1; i < weight.length + 1; i++) { 
      for (int k = 1; k < targetSum + 1; k++) { 
       if (k < weight[i - 1]) { 
        weightValMatrix[i][k] = weightValMatrix[i - 1][k]; 
       } else { 
        int valueInclusiveCurrentWeight = value[i - 1]; 
        if ((k - weight[i - 1]) > 0) { 
         valueInclusiveCurrentWeight = valueInclusiveCurrentWeight 
           + weightValMatrix[i - 1][k - weight[i - 1]]; 
        } 

        int valueExcludingCurrentWeight = weightValMatrix[i - 1][k]; 
        weightValMatrix[i][k] = valueInclusiveCurrentWeight >= valueExcludingCurrentWeight ? valueInclusiveCurrentWeight 
          : valueExcludingCurrentWeight; 

       } 

      } 



     } 



     for (int i = 1; i < weight.length + 1; i++) { 

      for (int k = 1; k < targetSum + 1; k++) { 

       System.out.print(weightValMatrix[i][k]); 

       if(k == targetSum){ 
        System.out.println(""); 
       } 
      } 
     } 


     System.out.println("final value is " + weightValMatrix[weight.length][targetSum]); 

     List<Integer> finallySelectedWeightIndex = new ArrayList<Integer>(); 

     findActualWeightIndex(weightValMatrix, weight.length, targetSum, finallySelectedWeightIndex, weight); 

     for(int index:finallySelectedWeightIndex){ 
      System.out.println("weight is " + weight[index-1] + " value is "+ value[index-1]); 
     } 


    } 


    public static void findActualWeightIndex(int[][] weightValMatrix, int row, int column, 
      List<Integer> finallySelectedWeightIndex, int[] weight) { 

     if(row==0 || column==0){ 
      return; 
     } 

     if(weightValMatrix[row][column]==weightValMatrix[row-1][column]){ 
      findActualWeightIndex(weightValMatrix, row-1, column, finallySelectedWeightIndex, weight); 
     }else{ 
      finallySelectedWeightIndex.add(row); 
      findActualWeightIndex(weightValMatrix, row-1, column - weight[row-1] , finallySelectedWeightIndex, weight); 
     } 
    } 

}