модификация Задачи о ранце (рюкзаке)

[razval]

доброго времени суток.
постановка задачи:
с клавиатуры вводиться массив элементов, каждый элемент имеет свой вес, требуется разбить этот масcив на двое, так что бы суммы элементов новых массивов были наиближайщие.
пример:
ввод:
4, 2, 11, 9
вывод:
общий вес: 26
первый массив: 11, 2
вес: 13
второй массив: 9, 4
вес: 13
не могу разобраться с индексацией в массивах(
листинг на cpp

#include <iostream>
using namespace std;
const int u=5, y=5;
main()
{
int n; //количество вещей
int j;//вес вещей
int k[j]; //массив для хранения вещей
int mas1[u]={0,0,0,0,0};//рюкзак 1
int mas2[y]={0,0,0,0,0};//рюкзак 2
int i=0; //счетчик
int sum=0,sum1=0,sum2=0; //общий вес
cout<<"введите количество вещей: ";
cin>>n;
while(i<n)
{
++i;
cout<<"введите вес вещи № "<<i<<": ";
cin>>k[i]; 
sum+=k[i]; 
};
cout<<"общий вес: "<<sum<<endl;
//сортировка
for(i=n; i>=1; --i)
for(j=1; j<i; ++j)
{
if(k[j]<k[j+1])
{
int m=k[j];
k[j]=k[j+1];
k[j+1]=m;		  
}
}
//вывод сортировки
/*	 for(i=1; i<=n; ++i)
{
cout<<k[i]<<" ";
} */
/*тут нужно что-то сделать с индексацией, 
чтобы он перебирал элементы массива k 
и по весу раскидывал в два массива ???*/
for(int i=1; i<=n; ++i)//просмотр всех вещей
{
if (sum1>=sum2)
{
for(int l=1; l<5; ++l)
{
mas1[0]=k[1];  
}
for(int i=0; i<5; ++i)			
{
sum1+=mas1[i];					
}
}
else
{
mas2[0]=k[2];

for(int i=0; i<5; ++i)
{
sum2+=mas2[i];
}
}
}
//вывод массивом и их сумм
cout<<"первый рюкзак: ";
for(int i=0; i<5; ++i)
{
cout<<mas1[i]<<" ";
}
cout<<endl;
cout<<"вес первого рюкзака: "<<sum1<<endl;
cout<<"второй рюкзак: ";
for(int i=0; i<5; ++i)
{
cout<<mas2[i]<<" ";
}
cout<<endl;
cout<<"вес второго рюкзака: "<<sum2;
getchar(); 
getchar();
}

 

[StudyMen]

Профессиональная и оперативная помощь студентам в решении задач по программированию.
Реализатор: ведущий разработчик. Более 5000 выполненных работ по программированию для студентов всех ВУЗов России более чем на 25 различных языках программирования.
Стоимость: от 30 рублей за задачу.
Оплата: оплата производится после выполнения задачи (то есть без предоплаты).
Способ оплаты: электронный платежные системы webMoney и Яндекс-деньги.
Контакты для связи:
Email: administrator@studymen.ru
Skype: studymen
ICQ: 639151387

 

[IrineK]

Индексация массива не имеет отношения к сумме весов.
Кроме того, сортировка по возрастанию тоже не поможет, если составляющие элементы будут неоднородными. Например: {1;1;11;1}. Тогда едиственным решением с минимальным разрывом будет {1;1;1} в один рюкзак и {11} - во второй. Общая сумма: S = 14, сумма первого рюкзака S1 = 3, второго S2=11. Разрыв: 14 - 2*3 = 8

Поскольку размерность N исходного набора невелика (ограничимся N<=8), можно организовать полный перебор всех возможных сочетаний без повторений: С(1;N), C(2;N)...C(N-1;N). Для каждого сочетания (k) нужно посчитать сумму составляющих элементов Sk.
Условием оптимальности будет требование к разрыву: S-2Sk ->min

Нужно организовать вывод сответствующего набора (можно сформировать строку из номеров элеметов), его сумму Sk(вес) и минимальный разрыв (S-2Sk)

 

[razval]

Поскольку размерность N исходного набора невелика (ограничимся N<=8), можно организовать полный перебор всех возможных сочетаний без повторений: С(1;N), C(2;N)...C(N-1;N). Для каждого сочетания (k) нужно посчитать сумму составляющих элементов Sk.
Условием оптимальности будет требование к разрыву: S-2Sk ->min
Нужно организовать вывод сответствующего набора (можно сформировать строку из номеров элеметов), его сумму Sk(вес) и минимальный разрыв (S-2Sk)

а можно хотя бы немного кода или псевдокода, этого куска

 

[IrineK]

ОК. Вот решение для частного случая: общего набора из 4 элементов

#include <iostream>
using namespace std;

const int n=4;//только для набора из 4 элементов
const int m=14;//количество всех возможных сочетаний при раскладке в 2 рюкзака

void 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;
S+=set;//определение общей суммы
}

//----------сочетания С(1;4),1 элемент из 4

for (i=0;i<n;i++)
{
Si[cur]=set;
descr[0][cur]=set;
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+set[j];
descr[0][cur]=set;
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+set[j]+set[k];
descr[0][cur]=set;
descr[1][cur]=set[j];
descr[2][cur]=set[k];
cur++;
}
//---------вывод всех наборов и сумм
cout<<"-----------------------------------------------------------"<<endl;
for (i=0;i<m;i++)
cout<<"Bag "<<descr[0]<<","<<descr[1]<<","<<descr[2]<<"; Si = "<<Si<<endl;

//--------поиск оптимального набора
int min=S;//самое большое число в рамках задачи

for (i=0;i<m;i++)
if (abs(S-2*Si)<min)
{
min=abs(S-2*Si);
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;

}

Попробуйте ваш исходный {4,2,11,9}, мой исходный {1,1,11,1}, а также любой другой.

 

[razval]

to IrineK

Спасибо, интересный вариант.

 

[dreamer]

Кроме того, сортировка по возрастанию тоже не поможет

Зато сортировка по убыванию поможет.

 

[IrineK]

Зато сортировка по убыванию поможет.

С этого места поподробней, пожалуйста.

 

[dreamer]

Из исходного массива выбираются элементы от большего к меньшему. На каждой итерации сравнивается сумма имеющихся в двух массивах элементов и текущий элемент добавляется в тот массив, в котором сумма меньшая. Таким способом достигается минимальная разница между суммами.

 

[IrineK]

Реализация отличной идеи dreamer для любого N:

#include <iostream>
using namespace std;

int lot[100],bag1[99],bag2[99];
int i;

void create_lot(int dim)
{
for(i=0;i<dim;i++)
{cout<<(i+1)<<": ";
cin>>lot[i];}
}

void arrange_lot(int dim)
{
int j,cur;
for(i=0;i<dim-1;i++)
for(j=i+1;j<dim;j++)
if(lot[i]<lot[j])
{	cur=lot[i];
lot[i]=lot[j];
lot[j]=cur;	}
}

void arrange_bags(int dim)
{
int sum1=0, sum2=0, k1=0, k2=0;
for(i=0;i<dim;i++)
{
if(sum1<=sum2)
{	bag1[k1]=lot[i];
sum1+=lot[i];
k1++;}
else
{	bag2[k2]=lot[i];
sum2+=lot[i];
k2++;}
}
cout<<"\nBag1: ";
for(i=0;i<k1;i++)
cout<<bag1[i]<<" ";
cout<<"\nSum1: "<<sum1<<endl;
cout<<"\nBag2: ";
for(i=0;i<k2;i++)
cout<<bag2[i]<<" ";
cout<<"\nSum2: "<<sum2<<endl;
}

void main()
{
int n;
cout<<"Total number of items is: ";
cin>>n;
create_lot(n);
arrange_lot(n);
arrange_bags(n);
}

Более того, данная идея позволяет формировать любое к-во рюкзаков M<=N. Возьму на вооружение. Спасибо.