将 10 个随机数分成两个列表的最简单方法是什么，其中列表总和的差异尽可能小

Question

你会得到10个数字，你必须将其分成两个列表，其中列表中的数字总和具有最小的差异。

因此，假设您得到：

10 29 59 39 20 17 29 48 33 45

您将如何将其分为两个列表，其中列表总和的差异尽可能小

所以在这种情况下，答案（我认为）将是：

59 48 29 17 10 = 163

45 39 33 29 20 = 166

我使用mIRC脚本作为语言，但perl或C++对我来说同样好。

编辑：实际上可以有多个答案，例如在这种情况下，它也可能是：

59 48 29 20 10 = 166

45 39 33 29 17 = 163

对我来说，只要最终结果是列表总和的差异尽可能小，这并不重要

编辑 2：每个列表必须包含 5 个数字。

Answer 1

您列出的正是分区问题（有关更多详细信息，请参阅 http://en.wikipedia.org/wiki/Partition_problem）。关键是这是一个NP完全问题，因此它不存在能够解决该问题的任何实例（即具有更多数字）的程序。

但是，如果你的问题总是只有十个数字分成两个列表，每个列表正好有五个项目，那么也可以天真地尝试所有可能的解决方案，因为它们只有 p^N，其中 p=2 是分区数，N=10 是整数数，因此只有 2^10=1024 个组合， 并且每个只需要 O（N） 进行验证（即计算差异）。

否则你可以实现维基百科页面中描述的贪婪算法，实现起来很简单，但不能保证最优性，实际上你可以在 Java 中看到这个实现：

static void partition() {
    int[] set = {10, 29, 59, 39, 20, 17, 29, 48, 33, 45}; // array of data
    Arrays.sort(set); // sort data in descending order
    ArrayList<Integer> A = new ArrayList<Integer>(5); //first list
    ArrayList<Integer> B = new ArrayList<Integer>(5); //second list
    String stringA=new String(); //only to print result
    String stringB=new String(); //only to print result
    int sumA = 0; //sum of items in A
    int sumB = 0; //sum of items in B
    for (int i : set) {
        if (sumA <= sumB) {
            A.add(i); //add item to first list
            sumA+=i; //update sum of first list
            stringA+=" "+i;
        } else {
            B.add(i); //add item to second list
            sumB+=i; //update sum of second list
            stringB+=" "+i;
        }
    }
    System.out.println("First list:" + stringA + " = " + sumA);
    System.out.println("Second list:"+ stringB+ " = " + sumB);
    System.out.println("Difference (first-second):" + (sumA-sumB));
}

它不会返回一个好的结果：

First list: 10 20 29 39 48 = 146
Second list: 17 29 33 45 59 = 183 
Difference (first-second):-37