問題は次のとおりです。
あなたは N 個の数字を持っています (N はあなたが持っている数字の数を表します)。グループ内の数値の合計の差が最小限になるように、それらを 2 つのグループに分けます。
例:
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
等々。最終的に数字が 1 つしかない場合は、それを合計の低いグループに入れます。だから私は最終的に取得します：
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;
}