java - 将数组分成两个子数组，使数组的总和之间的差异最小？

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 的元素，那么这将解决您的问题最小化两个划分列表之间差异的问题。

背包问题的求解有一个标准的算法，这里不再赘述。