将数组划分为两个子数组,以便数组总和之间的差异最小？

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

这是背包问题.在一般情况下它是NP完全的,但对于小整数,它可以有效地解决.

我们来看看你的示例数组吧[4,13,14,15,16].总数是62.我们将其改为背包问题,我们有这套项目,但背包容量是62÷2 = 31.如果我们选择总数不超过31的项目,那么这解决了你的问题最小化两个划分列表之间差异的问题.

有一个解决背包问题的标准算法,我在这里不再解释.