Ste*_*024 10 c++ algorithm combinations numbers
这是问题所在:
您有N(N代表您拥有的数字)数字.将它们分成两组,使得组中数字之和的差异最小.
例子:
5 // N
1, 9, 5, 3, 8 // The numbers
如果我们在A组中放置1,9和3,在B组中放置5和8,则差异为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;
}
使用仅两组的约束，如果您可以找到一组数字，其总和恰好是总数的一半，那么我们的问题就已经解决了。因此我建议你尝试找到这个组并将剩余的显然放入另一个组。
将最大数字放入第一组的假设很简单。现在剩下的事情就更加棘手了。
这在二进制系统中很简单：考虑每个数字都有一个位。该位发出信号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。这是我在这里找到的克纳思书的链接
edit2：按要求解释枚举的概念：
假设我们有三个元素，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 组中）。因此，while Ais 。1B23,5
现在解释一下为什么我只需要看一半的技巧：如果我们看一下十进制解释3（011二进制），我们会得到 GroupA 23,5和 Group B 1。如果我们将其与示例进行比较，4我们会注意到我们分组了相同的数字，只是组名称完全相反。由于这对您的问题没有影响，我们不必考虑这个。
edit3：我添加了真实的代码来尝试，在伪代码中我做出了错误的假设，即我总是在总和中包含第一个元素，这是错误的。至于我开始的代码：你不能这样分配数组。另一种替代数组的解决方案是 a vector<int>，它避免了必须将数组大小传递给函数的问题。使用这个将会有很大的改进。此外，这段代码还很不好。您将遇到问题int size（通常这最多适用于 32 个元素）。不过，您可以解决这个问题（尝试一下如何处理任意大的整数）。或者您实际上阅读了 knuth （见上文），我相信您会找到一些递归方法。该代码也很慢，因为它总是重建整个总和。一种优化是研究格雷码（我认为 Knuth 也描述了它们）。这样，您只需为测试的每个排列添加/减去一个数字。这将带来大约 的性能提升n，因为您n-1用1加法/减法替换了加法。