Поскольку размерность N исходного набора невелика (ограничимся N<=8), можно организовать полный перебор всех возможных сочетаний без повторений: С(1;N), C(2;N)...C(N-1;N). Для каждого сочетания (i) нужно посчитать сумму составляющих элементов Si. i = (1...k)
Количество всех сочетаний k = 2^N - 2
Условием оптимальности будет требование к разрыву: |S-2Sk| ->min
Нужно организовать вывод сответствующего набора (можно сформировать строку из значений элементов), его сумму Sk(вес) и минимальный разрыв |S-2Sk|.
Ниже представлено решение на С++ для частного случая: общего набора из N = 4 элементов
#include <iostream>
using namespace std;
const int n=4;//только для набора из 4 элементов
const int m=14;//количество всех возможных сочетаний при раскладке в 2 рюкзака
int main()
{
int i,j,k,opt1,opt2;
int S=0;//общая сумма
int set[n]; //общий набор
int bag1[n-1]={0,0,0};//рюкзак 1
int bag2[n-1]={0,0,0};//рюкзак 2
int Si[m]; //суммы каждого из сочетаний
int descr[n-1][m];//описания каждого из сочетаний
int cur=0; //текущий индес для массивов сочетаний
cout<<"Specify the set of 4 numbers"<<endl;
for (i=0;i<n;i++)
{
cout<<"Number "<<(i+1)<<" ";
cin>>set[i];
S+=set[i];//определение общей суммы
}
//----------сочетания С(1;4),1 элемент из 4
for (i=0;i<n;i++)
{
Si[cur]=set[i];
descr[0][cur]=set[i];
descr[1][cur]=0;
descr[2][cur]=0;
cur++;
}
//----------сочетания С(2;4),2 элемента из 4
for (i=0;i<n-1;i++)
for (j=i+1;j<n;j++)
{
Si[cur]=set[i]+set[j];
descr[0][cur]=set[i];
descr[1][cur]=set[j];
descr[2][cur]=0;
cur++;
}
//----------сочетания С(3;4),3 элемента из 4
for (i=0;i<n-2;i++)
for (j=i+1;j<n-1;j++)
for (k=j+1;k<n;k++)
{
Si[cur]=set[i]+set[j]+set[k];
descr[0][cur]=set[i];
descr[1][cur]=set[j];
descr[2][cur]=set[k];
cur++;
}
//---------вывод всех наборов и сумм
cout<<"-----------------------------------------------------------"<<endl;
for (i=0;i<m;i++)
cout<<"Bag "<<descr[0][i]<<","<<descr[1][i]<<","<<descr[2][i]<<"; Si = "<<Si[i]<<endl;
//--------поиск оптимального набора
int min=S;//самое большое число в рамках задачи
for (i=0;i<m;i++)
if (abs(S-2*Si[i])<min)
{
min=abs(S-2*Si[i]);
opt1=i;
}
opt2=m-opt1-1;// используем симметрию задачи
cout<<"-----------------------------------------------------------"<<endl;
cout<<"Optimum Bag1: "<<descr[0][opt1]<<","<<descr[1][opt1]<<","<<descr[2][opt1]<<"; Si = "<<Si[opt1]<<endl;
cout<<"Optimum Bag2: "<<descr[0][opt2]<<","<<descr[1][opt2]<<","<<descr[2][opt2]<<"; Si = "<<Si[opt2]<<endl;
return 0;
}
|