Комбинаторика

[music66]

У вас есть несколько камней известного веса W1, …, Wn. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.

Исходные данные
Ввод содержит количество камней N (1 ≤ N ≤ 20) и веса камней W1, …, Wn (1 ≤ Wi ≤ 100 000) — целые, разделённые пробельными символами.

Результат
Ваша программа должна вывести одно число — минимальную разность весов двух куч.

Пример
___________________________

исходные данные |результат
___________________________
5|
___________________________
5 8 13 27 14 |3

P.S.
Пыталась решить двумя способами:
1) Сортировка массива масс камней по возрастанию, а далее попеременное сложение масс камней с начала и с конца массива в две кучи (а центральные в ту кучу, где сумма масс меньше), т.е.
1 4 76 78 190 200
1 кучка | 2 куча
1 200 | 4 190
78 | 76

2) 1 2 3 4 5 6 7
Сначала сложение каждого элемента массива с одним из последующим, а сумма остальных во второй массив.
После сложение каждого элемента массива со всеми последующими, а сумма остальных во второй массив.
Каждый раз запоминается сумма в каждом из массивов, далее выбирается минимальное и находится вариант, при котором этот минимум был достигнут.


В итоге ничто из этого нормально не работает.

Если кто поможет, заранее благодарю.

[Vago]

http://programmersforum.ru/showthread.php?t=144760
Единственно, фразу "Из оставшихся, опять беруться два и к самому лёгкому (лёгкой группе) из уже образованных, добавляется самый тыжёлый." следует читать: "из оставшихся берётся самый тяжёлый и добавляется к "более лёгкой" группе".

[music66]

Спасибо за помощь неумеющему юзать поиск
Жаль C только в следующем семестре)))
Если не сложно переведите на Delphi

[Vago]

А зачем "переводить"-то? Там есть словесное описание алгоритма. Берёте и просто пишете на том языке, который знаете...

[music66]

Преподаватель сказал что нужно делать перебором и этот вариант ему не нравится

[Mandrivnyk]

Как вариант.
Находишь общую сумму камней, делишь ее пополам -- получаешь вес кучи для идеального распределения.
Сортируешь массив по убыванию.
Берешь первый элемент (максимальный), если он больше или равен весу идеальной кучи -- все, поиск окончен (в первой куче будет только он, во второй -- все остальные); если нет -- вычитаешь его вес из веса идеальной кучи, остаток запоминаешь.
Берешь второй элемент, если он равен остатку -- конец, идеальное распределение; если он больше остатка -- берешь следующий; если меньше -- пересчитываешь остаток и повторяешь все для следующего элемента; в идеальном случае в процессе перебора остаток должен уйти в 0.
Если этого не происходит до конца перебора, запоминаешь последний остаток -- это и будет разница весов двух куч; после чего возвращаешься на шаг назад -- берешь элемент не (n), а (n+1) (то есть один элемент пропускаешь). Опять проходишь до конца перебора и сравниваешь новый остаток (разницу весов двух куч) с минимальным на данный момент.
Ну и так далее...

Надеюсь, я понятно озвучил идею -)

[Serge_Bliznykov]

Преподаватель сказал что нужно делать перебором и этот вариант ему не нравится

возьмите решение val_nnm с перебором.
отсюда: http://programmersforum.ru/showpost....40&postcount=7

проверил. вроде бы правильно работает.

[music66]

Спасибо за помощь, ребята!

[music66]

опять проблема..
в этой проге (что выше) используются функции, которые мы еще не изучали => будет ясно что написано не мной. Это shl и shr. Как можно заменить их?

[Вадим Мошев]

Это shl и shr.

Это соответственно порязрядный сдвиг влево и вправо.

shl (сдвиг влево) эквивалентен простому умножению на 2
shr (вправо) эвивалентен целочисленному делению на 2.

PS: всё выше написанное верно, если я не ошибаюсь.