c++ - 对数字进行分组 C++

Question

问题是:

您有 N 个(N 代表您拥有的数字的个数)个数字。将它们分成 2 组，以使各组中数字之和之间的差异最小。

例子:

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

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

您建议计算出数字的总和并将其除以二是正确的起点 - 这意味着您知道每组的理想总和是多少。我还怀疑你最好的选择是首先将最大的数字放入组 A。/p>

这是我们进入启发式的时候，您可以循环进行启发式直到完成分组:

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.

毫无疑问会有失败的情况，但作为一种粗略的方法，这应该经常接近。要实际编写上述代码，您需要将数字放在有序列表中，以便很容易从大到小处理它们。 (然后也可以通过检查(针对两个“到目前为止的组”)从最大的剩余向下直到添加到被检查的数字的“到目前为止的组”比 t 低 1.0 以上来简化步骤 1 - 之后无法满足条件.)

如果这有效，请告诉我!