1

你得到 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 个数字。

4

1 回答 1

0

您列出的正是分区问题（有关更多详细信息，请参见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
于 2014-04-04T14:30:54.323 回答