доработать алгоритм сравнения чисел.

[GoldSieg]

Доброго времени суток.
задача. пользователь вводит некоторое кол-во чисел(отрезков времени)к примеру 8. программа должна разбить на 2 кучи эти числа, чтобы сумма в каждой кучке была примерно равна.
Пример: числа 1,2,3,4,5,6,7,8 должно распределить кучка1(1+2+4+5+6=18) и кучка2(3+7+8=18).
мой код .

int main()
{
int size = 8; 
int full_time_1 = 0;
int full_time_2 = 0;

struct potok 
{ 
	int time; 
	int CPU; 
}
*Potok = new potok [size];

{

	for(int count1 = 0; count1 < size ; count1++)
	{
		Potok[count1].time = 0; 
	}
	
	cin>>(Potok[0].time); 
	cin>>(Potok[1].time); 
	cin>>(Potok[2].time);
	cin>>(Potok[3].time); 
	cin>>(Potok[4].time); 
	cin>>(Potok[5].time); 
	cin>>(Potok[6].time);
	cin>>(Potok[7].time);
	
	
    full_time_1 = Potok[0].time;
    full_time_2 = Potok[1].time;
	for(int count2 = 2; count2 < size; count2++)
	{
		  if  (full_time_1 < full_time_2)  full_time_1 = full_time_1 + Potok[count2].time ; 
	else
          full_time_2 = full_time_2 + Potok[count2].time ; 
		
	}
	
	cout<<"время №1"; 
	cout<<(full_time_1);
	cout<<" ";
	cout<<"\n время №2:  ";
	cout<<(full_time_2);
    cout<<" ";
	cout<<"\n максимальное время";
	if ( full_time_1 >= full_time_2)
		cout<<(full_time_1);
	else cout<<(full_time_2);
	cout<<" mc";
	cout<<" \n общее время ";
	cout<<(full_time_1 + full_time_2);
	cout<<" mc";

	 //system("PAUSE > void");
}
}

p/s желательно обойтись без банальной сортировки=))))

[Serge_Bliznykov]

посмотрите на эту тему.
возможно, что ссылки в пост #2 немного Вам помогут.
Успехов!

p.s.

p/s желательно обойтись без банальной сортировки=))))

там в алгоритме используется "банальная" сортировка, если Вам нужно без неё (кстати, непонятно почему ), тогда по ссылке можно не ходить...

[nikmoon]

Полностью согласен со вторым постом.

[GoldSieg]

Serge_Bliznykov,
за ссылку конечно благодарствую, но мне мне интерестно как можно без сортировки обойтись.

[Shad0wF1rst]

А если решить задачу в лоб? Тут понятное дело нужны знания в комбинаторике. Во первых нужно вычислить количество комбинаций без повторения. Ну вот смысл в том чтобы запомнить разность полученных ответов от этих самых кучек, соответственно по модулю, и эту минимальную разность считать ответом. А что касается реализации функции в которой будет разбиваться на кучки, то это конечно нужно продумать сейчас времени на это нет но задачка интересная. ТО есть примерно должно работать так:
итерация1:
мин = 1+2+3+4+5+6+7+8;
куч1 = 1;
куч2 = 2+3+4+5+6+7+8;
if (мин > abs(куч1-куч2)) мин = abs(куч1-куч2)
итерация2:
куч1 = 1+2;
куч2 = 3+4+5+6+7+8;
if (мин > abs(куч1-куч2)) мин = abs(куч1-куч2)
итерация2:
куч1 = 1+3;
куч2 = 2+4+5+6+7+8;
if (мин > abs(куч1-куч2)) мин = abs(куч1-куч2)

И так далее пока не найдется нужные кучки. Но алгоритм надо продумать до конца. Единственное время выполнение одних и тех же участков кода может разнится.

[GoldSieg]

Shad0wF1rst,Вот!. мне тоже эта задача показалась очень забавной, но все составленные мной условия заваливались.
Предложенный вами код конечно работать будет. но что если переменных будет не 8, а 108?) как бы так делать что было универсально.)

[Shad0wF1rst]

Сообщение от GoldSieg

Shad0wF1rst,Вот!. мне тоже эта задача показалась очень забавной, но все составленные мной условия заваливались.
Предложенный вами код конечно работать будет. но что если переменных будет не 8, а 108?) как бы так делать что было универсально.)

Оно все также работать будет, эти все операции сложения в кучках делаются в цикле, но самый большой минус это увеличение времени работы, причем очень сильно с увеличением количества алиментов. Что соответственно не есть хорошо. Но если исключить подобные ситуации, как : куч1 = 1+2+3 и куч1 = 1+3+2 то соответственно сократится время работы, но алгоритм нужно продумать как это сделать.

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

[GoldSieg]

Если работать с отсортированым массивом, то чем плоха моя программа вроде с любыми значениями работает оптимально.

full_time_1 = Potok[0].time;
    full_time_2 = Potok[1].time;
	for(int count2 = 2; count2 < size; count2++)
	{
		  if  (full_time_1 < full_time_2)  full_time_1 = full_time_1 + Potok[count2].time ; 
	else
          full_time_2 = full_time_2 + Potok[count2].time ; 
		
	}

[Shad0wF1rst]

Сообщение от GoldSieg

Если работать с отсортированым массивом, то чем плоха моя программа вроде с любыми значениями работает оптимально.

full_time_1 = Potok[0].time;
    full_time_2 = Potok[1].time;
	for(int count2 = 2; count2 < size; count2++)
	{
		  if  (full_time_1 < full_time_2)  full_time_1 = full_time_1 + Potok[count2].time ; 
	else
          full_time_2 = full_time_2 + Potok[count2].time ; 
		
	}

Может я не понял условия задачи, но данный ваш код работает предположим full_time_1 < full_time_2? то full_time_1 = full_time_1 + Potok[count2].time будет выполняться всегда, то есть в вашем примере: full_time_1 = 1, а full_time_2 = 2, следовательно full_time_1 = full_time_1 + 3+ 4+5+6+7+8, в full_time_2 так и останется 2 и поровну явно ничего не поделится.

Сорри написал чушь выше, единственная рекомендация начинать с больших чисел и идти на уменьшение

Для убедительности своих слов относительно обратного порядка следования от больших чисел к меньшим скажу что при использования прмого порядка от 2..size для вашего примера где числа от 1..8 получаются числа 16 и 20 при обратном же получается 18 18

[GoldSieg]

я имел ввиду, что моё условие будет работать оптимально в отсортированном по убыванию. т.е 1е два будут самыми большими значениями, но как без сортировки, то сделать).

з.ы подскажите как правильно параметры кода в шапке в функцию передать.

int sortt(int size, int *a[])
{
	for (int i=0;i<10;i++){
		for (int j=0;j<9;j++){
			if (a[j]<a[j+1]) {int prom=0; prom=a[j];a[j]=a[j+1];a[j+1]=prom;}; }};
			
			for (int xxx=0;xxx<10;xxx++){
				cout<<a[xxx];    };

				system("PAUSE");
				return ;
}