Нужны задачки

[rumpelstilzchen]

правильно сказал Finch, что это жадный алгоритм. Скупой платит дважды.
имеем камни (кг) 1, 2, 3, 4. По твоему, алгоритму, получается две кучи 4 (1 и 3) кг и 6 (2 и 4)кг.
Оптимальный вариант -  1 и 4, 2 и 3.
Задача осталась не решенной. Мой вариант есть. Могу выложить. Выложить? Только в псевдокоде.

[Джон]

Лёш, я не подбираю две кучки камней с одинаковой массой. Я НАБИРАЮ из ВСЕХ камней массу равную половине исходной массы. Конечно я сначала её отсортирую. А потом перебеор будет уже оптимирован.

Согласен, что ты сделаешь перебор быстрей. Но вот только будет ли это решением задачи, требованием которой является минимальная разница? Это носит вероятностный характер. Повезёт - да, но в самом общем случае - нет.

[Джон]

Задача осталась не решенной. Мой вариант есть. Могу выложить. Выложить? Только в псевдокоде.

А чем тебе мой не подходит?

[Алексей++]

rumpelstilschen, по моему алгоритму получается:
-------------
1) куча: 1,2,3,4
н1:пусто
н2:пусто

ищем самый тяжелый , это 4

2) куча: 1,2,3
н1: 4
н2:пусто

масса набора 1 больше набора 2, переключаемся на набор 2
ищем самый тяжелый , это 3

3)
куча: 1,2
н1: 4
н2: 3

масса набора 2 НЕ больше набора 1
ищем самый тяжелый , это 2

4)
куча: 1
н1: 4
н2: 3,2

масса набора 2 больше набора 1, переключаемся на набор 1
ищем самый тяжелый , это 1

5)
куча: пусто
н1: 4,1
н2: 3,2

-------------


Джон, нету там никакой вероятности, алгоритм обеспечит точную подгонку, согласись. Или покажи глюк


rumpelstilschen, давай своё решение

[rumpelstilzchen]

Джон: да, решений много и твой работает.

Алексей1153++: у меня просто другой алгоритм. сейчас, найду и покажу

[Алексей++]

это просто клёво, когда есть много решений

[Sla]

В футбол в детстве играли?
Два человека начинают поочередно набирать себе команду
в результате почти одинаковые команды получались

Здесь же можно пойти по другому пути
Тяжелый - легкий

Но! в таком случае количество камней в кучах будет одинаково.

[Sla]

вот например
4 3 1 2
первая куча 4 1
вторая 3 2

но, а если
4 3 1?
первая куча 4
вторая 3 1
моя пошла думать...

[Алексей++]

Слав, всё правильно , и даже если
10,1,1,1,1,1,1

будет

10
1,1,1,1,1,1

всё, сходицо

[rumpelstilzchen]

1. 4 камня, возводим в квадрат. Получаем 16 блоков.
2. в каждом блоке по 2 секции - "кучи"
3. распределяем каждый камень таким образом, чтобы он прошел по каждой куче, каждого блока, но так, чтоб "свзаимодействовал" с каждым камнем, рапределенным таким же способом.
4. в каждом блоке вычитаем из большей кучи, кучу меньшую.
5. получаем результат наименьшего значения по требуемому условию

Плюсы: нейронная сортировка.
Минусы: большой объем задействованных ресурсов, если использовать линейный метод. При оптимизации, ресурсо-требуемость сокращается.

[Алексей++]

1. 4 камня, возводим в квадрат. Получаем 16 блоков.

ага... 100000 камней возводим в квадрат... Таких кампутеров тогда ещё не было

2. в каждом блоке по 2 секции - "кучи"
3. распределяем каждый камень таким образом, чтобы он прошел по каждой куче, каждого блока, но так, чтоб "свзаимодействовал" с каждым камнем, рапределенным таким же способом.
4. в каждом блоке вычитаем из большей кучи, кучу меньшую.
5. получаем результат наименьшего значения по требуемому условию

а зачем именно так? Тем более, что и непонятно. Если хочется перебрать все варианты сочетаний из N камней - заведи N*2 -разрядное двоичное число, и инкреминируй от 0 и до переполнения (2^(N*2)) .
Отсеивай только те числа, в которых 10 бит.
Интерпретируй так: первые Nбит - маска для первого набора, последние N бит - маска для второго.
Также отсеивай случаи, когда биты в масках пересекаются (то есть когда Mask1 & Mask2 не равно 0)

из подходящих сочетаний выбери те, которые имеют меньшую разницу в суммарной массе. Усё.

Код:

Плюсы: нейронная сортировка.

где тут нейроны?

Код:

Минусы: большой объем задействованных ресурсов, если использовать линейный метод. При оптимизации, ресурсо-требуемость сокращается.

ага, много кода, много озу

[rumpelstilzchen]

>где тут нейроны?

камни

[Алексей++]

это круто. Зачем такая самокритика, не надо

[rumpelstilzchen]

взаимодействие между камнями - нейронные связи.
нейронных связей в мозгу человека - больше чем атомов во вселенной. )

[Алексей++]

ну про атомы во вселенной это ты конечно загнул... Если бы ДАЖЕ каждая связь состояла из одного атома, то этого бы всё равно не получалось бы

нейрон - это запоминающий элемент со связями (камень не катит)

Кстати, ещё можно было бы использовать генетический алгоритм, озу потребуется с понты, но долго вычисляться будет

[rumpelstilzchen]

>генетический алгоритм

это что?

[Sla]

вот...
1 куча -> самый тежелый из остатка
проверка на вес кучи с весом последнего тяжелого камня из остатка
2 куча -> самый тяжелый из остатка или вся оставшаяся куча

4 1 1 1
1. 4
2. 1 1 1

4 3 2
здесь можно ввести еще одно условие на проверку... (отдав предпочтение последнего камня второй куче)
1. 4
2. 3 2

9 8 3 2 1 1 1 1
1. 9 1 3
2. 8 1 2 1 1

[Алексей++]

rumpelstilschen, это алгоритм, где моделируется содранный у природы естественный отбор , вкратце не смогу рассказать - сам никогда не пользовался. Поищи. Штука занятная ) . Там правила некоторые (так же из природы) - каков процент мутации параметров, перекрёстный обмен генами, передача наследственности. Ну и вычисляется это всё долго, конечно

[Алексей++]

Слав, а в моём алгоритме получается
1:9211
2:8311

[Sla]

Алексей1153++, в твоем алгоритме уравнивается команды в правах, предпочтение отдается слабому...

+1

[Алексей++]

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

[rumpelstilzchen]

Алексей1153++, твой алгоритм надо тестировать. а мой не надо.

[Алексей++]

да твой ещё не написан, а мой вовсю работает ) Покажи мне исходные данные, при которых будет косяк?

[rumpelstilzchen]

>Покажи мне исходные данные, при которых будет косяк?

Алексей1153++, говорю, не знаю, тестировать нужно. Сам алгоритм тестировать. Не прогу.

[Sla]

rumpelstilschen, так мы его уже оттестировали
А почему твой тестировать не надо? У тебя что самопроверяющийся алгоритм?
А у Лешки работающий, даже в тяжелых условиях.

[Sla]

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

не, ты отдаешь предпочтение слабой куче...

[Алексей++]

rumpelstilschen , программу я не писал, я на работе, другой программой занят. А алгоритм интуитивный. А давай, напиши программу , если не лень, заодно и проверим ) И RND прикрути для тестов

[rumpelstilzchen]

Sla, мой тестировать не надо, потому что он рассматривает все варианты конфигурации камней, и выбирает тот, который требуется по условию.

Алексей1153++, сейчас нет. я занят. на мне 2 курсовика висят )

[Алексей++]

курсовики, говоришь... А вот программа

Код:

{
	//исходная куча
	const int SourceHeap[]={1,2,3,4,5,6,7,8,9};

	int N=sizeof(SourceHeap)/sizeof(*SourceHeap);

	//рабочая куча
	int* WorkCommonSet=new int[N];
	::memmove(WorkCommonSet,SourceHeap,N*sizeof(*SourceHeap));

	//наборы
	int* Set1=new int[N];
	int* Set2=new int[N];
	::memset(Set1,0,N*sizeof(*Set1));
	::memset(Set2,0,N*sizeof(*Set2));

	//не сортируем WorkCommonSet, будем так искать максимальный
	//элемент, а потом заменять на 0 после использования

	int S=1;//текущая куча
	int W1=0;//вес набора 1
	int W2=0;//...2
	int N1=0;//камней в наборе 1
	int N2=0;//...2

	for(;;)
	{
		//ищем в общей куче максимальный элемент, вес его - maxStoneW
		int maxStoneW=0;
		int* pMax=0;

		int* p=WorkCommonSet;
		for(int i=0;i<N;i++,p++)
		{
			if(*p)
			{
				if(*p > maxStoneW)
				{
					maxStoneW=*p;
					pMax=p;
				}
			}
		}

		//если не найдено ничего - выход
		if(!maxStoneW)break;

		//вытаскиваем камень из общей кучи
		*pMax=0;


		if(S==1)
		{
			//кладём камень в набор 1
			Set1[N1]=maxStoneW;
			N1++;
			W1+=maxStoneW;

			if(W1>W2)
			{
				S=2;
			}

		}
		else
		{
			//кладём камень в набор 2
			Set2[N2]=maxStoneW;
			N2++;
			W2+=maxStoneW;

			if(W2>W1)
			{
				S=1;
			}
		}
	}
//Set1 и Set2 - результат , N1 и N2 - длины массивов
	delete [] WorkCommonSet;
	WorkCommonSet=0;

	delete [] Set1;
	Set1=0;

	delete [] Set2;
	Set2=0;

}

[rumpelstilzchen]

я не провел алгоритм по исходнику. должно получится 2 кучи. 22 кг и 23 кг. получил ехешник? дай посмотреть. и исходник тоже, полностью.

ты удалил указатель           >  delete [] Set1;
а потом его инициализируешь   >  Set1=0;

разве так можно?