对数字 C 进行分组

Question

问题是：

你有N (N代表你拥有的数字的数量)个数字。将他们分成两组，使各组数字之和的差异最小。

例子：

5 // N

1, 9, 5, 3, 8 // The numbers

如果我们把1、9和3放在A组，把5和8放在B组，差异是0。

我认为首先我应该计算所有数字的总和并将其除以2。然后检查任何可能的数字组合，其总和不大于所有数字之和的一半。完成此操作后，我将选择最大的数字并打印出组。

我对所有的组合都有问题，特别是当N是大数字时。如何运行所有组合？

我的想法也有点不同，我将按降序对数字进行分组，将最大的数字放在A组，最小的放在b组，然后反过来。这适用于某些数字，但有时它不能显示最佳分组。例如:

如果我用前面的例子。按降序排列数字。

9, 8, 5, 3, 1.

把最大的放在A组，最低的放在B组。

Group A: 9
Group B: 1

反过来。

Group A: 9, 3
Group B: 1, 8

诸如此类。如果最后我只有一个数字，我会把它放在总和较低的那一组。所以我最后会得到:

Group A: 9, 3
Group B: 1, 8, 5

这不是最佳分组，因为差异为 2，但以不同的方式分组时，差异可以是 0，正如我所展示的那样。

怎样才能得到最优分组？

法典：

#include <iostream>
#include <cmath>
#include <string>
using namespace std;
int convertToBinary(int number) {
    int remainder;
    int binNumber = 0;
    int i = 1;
    while(number!=0)
    {
        remainder=number%2;
        binNumber=binNumber + (i*remainder);
        number=number/2;
        i=i*10;
    }
    return binNumber;
}
int main()
{
    int number, combinations, sum = 0;
    double average;
    cin >> number;
    int numbers[number];
    for(int i = 0; i<number; i++)
    {
        cin >> numbers[i];
        sum += numbers[i];
    }
    if(sum%2 == 0)
    {
        average = sum/2;
    }
    else
    {
        average = sum/2 + 0.5;
    }
    combinations = pow(2,number-1);
    double closest = average;
    for(int i = 0; i<=combinations;i++)
    {
        int rem;
        int temp_sum = 0;
        int state = convertToBinary(i);
        for(int j = 0; state!=0; j++)
        {
            int rem =state%10;
            state = state/10;
            if(rem == 1)
            {
                temp_sum = temp_sum + numbers[j];
            }
        }
        if(abs(average-temp_sum)<closest)
        {
            closest = abs(average-temp_sum);
            if(closest == 0)
            {
                break;
            }
        }
    }
    cout << closest*2;
    return 0;
}

Answer 1

如果单个组的平均值与整个组的平均值相同，那么两个组之间的差异显然会更小。利用这一点，我们可以提出这个问题的算法。

1. 得到全套的平均值。
2. 取集合中最大的值，放在其中一组中。
3. 得到个体组平均值和整个集合平均值的差值。
4. 在差值最大的组中放置下一个最大的数字。
5. 重复步骤3和4，直到所有的数字都被放置。

这将是获得近似最优解的有效方法。

Answer 2

如果你能找到一组和正好是总数一半的数字，那么只使用两组数的约束，zour问题就已经解决了。因此，我建议你设法找到这一组，并将其余部分明显地放入另一组。

将最大数字放在第一组中的假设很简单。现在剩下的就更棘手了。

这在二进制系统中很简单：考虑每个数字都有一个位。1的位表示该数字在组A中，否则它在组B中。整个分布可以用这些位的串联来描述。这可以被认为是一个数字。要检查所有组合，你必须遍历所有数字并计算组合。

法典：

#include <iostream>
#include <memory>
using namespace std;

int partition(const std::unique_ptr<int[]>& numbers, int elements) {
    int sum = 0;

    for(int i=0; i<elements; ++i) {
        sum += numbers[i];
    }

    double average = sum/2.0;
    double closest = average+.5;

    int beststate = 0;


    for(int state=1; state< 1<<(elements-1);++state) { 
        int tempsum = 0;
        for(int i=0; i<elements; ++i) {
            if( state&(1<<i) ) {
                tempsum += numbers[i];
            }
        }

        double delta=abs(tempsum-average);
        if(delta < 1) { //if delta is .5 it won't get better i.e. (3,5) (9) => average =8.5
            cout << state;
            return state;
        }

        if(delta<closest) {
            closest   = delta;
            beststate = state;
        }
    }

    return beststate;
}

void printPartition(int state, const std::unique_ptr<int[]>& numbers, int elements) {
    cout << "(";
    for(int i=0; i<elements; ++i) {
        if(state&(1<<i)) {
            cout << numbers[i]<< ",";
        }
    }
    cout << ")" << endl;
}

int main()
{
    int elements;

    cout << "number of elements:";
    cin >> elements;

    std::unique_ptr<int[]> numbers(new int[elements]);

    for(int i = 0; i<elements; i++)
    {
        cin >> numbers[i];
    }

    int groupA = partition(numbers, elements);

cout << "\n\nSolution:\n";
    printPartition(groupA, numbers, elements);
    printPartition(~groupA,numbers, elements);
    return 0;
}

编辑:要获得更多(更好)的解决方案来产生所有的可能性，请查看这个awnser。这是我在这里找到的knuths的书的链接

编辑2:按照要求解释枚举的概念:

假设我们有三个元素，< code>1，23，5。不考虑排列的所有可能的组合可以通过填写表格来产生:

1 | 23 | 5         Concatination   Decimal interpretation
-----------
0 |  0 | 0         000                0
0 |  0 | 1         001                1
0 |  1 | 0         010                2
0 |  1 | 1         011                3
1 |  0 | 0         100                4
1 |  0 | 1         101                5
1 |  1 | 0         110                6
1 |  1 | 1         111                7

如果我们现在立即将数字4映射为100，表示第一个数字属于A组，第二个和第三个数字不属于B组（这意味着它们属于B组）。因此，A为1，而B23，5。

现在解释一下为什么我只需要看一半:如果我们看十进制解释< code>3 (011二进制)，我们得到组< code>A 23，5和组< code>B 1。如果我们将此与< code>4的示例进行比较，我们会注意到我们分组了相同的数字，只是组名完全相反。因为这对你的问题没有影响，所以我们不必看这个。

编辑3:我添加了真实的代码进行测试，在伪代码中，我做了一个错误的假设，即我将总是在总和中包含第一个元素，这是错误的。至于我开始写的代码:你不能像那样分配数组。代替数组的另一个解决方案是< code >向量

Answer 3

尽管正如其他人所评论的那样，这是一个NP-完全问题，但您提供了两个相当有用的边界：您只想将一组数字分成两组，并且您希望尽可能接近两组的总和。

你提出的计算数字的总和并将其除以二的建议是正确的起点 - 这意味着你知道每个组的理想和是什么。我还怀疑你最好的选择是把最大的数字放到A组开始（它必须进入一个组，这是以后最糟糕的一个，所以为什么不把它放在那里呢？

这就是我们进入试探法的时候，你循环通过，直到组完成:

N: Size of list of numbers.
t: sum of numbers divided by two (t is for target)

1. Is there a non-placed number which gets either group to within 0.5 of t? If so, put it in that group, put the remaining numbers in the other group and you're done.
2. If not, place the biggest remaining number in the group with the current lowest sum
3. go back to 1.

毫无疑问，会有失败的案例，但作为一种粗略的方法，这应该经常接近。要真正对上面的代码进行编码，您需要将这些数字放入一个有序的列表中，以便从最大到最小很容易地处理它们。（然后，也可以通过检查（针对两个“迄今为止的组”）来简化步骤1，从剩余的最大组向下检查，直到添加到被检查数字中的“迄今为止组”比t低1.0以上，然后条件就无法满足。）

如果可行，请告诉我！