将数组分成两个子数组，以便数组之和的差值最小？

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

}