Перебор!

← →
CanCan (2004-02-04 21:47) [0]

Здравствуйте!
Кто-нибудь объясните как происходит перебор вариянтов в след. задаче: есть кучка камне(20) нужно раскидать их на две кучки наиболее близкого веса. Может кто подскажет, Алгоритм как это делать.

← →
Johnmen © (2004-02-04 22:03) [1]

Критерий по кучкам неясен...

← →
CanCan (2004-02-04 22:07) [2]

Раскидать так, чтобы вес первой кучи был как можно больше равен 2ой кучи, т.е. разность сумм 1-ой кучи и второй кучи должны быть наименьшей. Я не могу представить как осуществить перебор, блин прсто хочу понять как ..

← →
Юрий Зотов © (2004-02-04 22:12) [3]

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

Из набора N чисел (N=20), сумма которых равна S сделать выборку, сумма чисел в которой максимально близка к S/2.

IMHO, это классическая задача линейного программирования. Посмотрите симплекс-метод.

← →
Chuha (2004-02-04 22:30) [4]

2Юрий Зотов
Большое спасибо :)
Не могли бы Вы объяснить как это сделать через перебор(просто нужно понять, а то вроде бы как делать знаю, но не могу :( ), просто алгоритм(если не трудно). За ранее спасибо :)

← →
dr Tr0jan © (2004-02-05 04:18) [5]

Народ, так это же знаменитая олимпиадная задача (описания в инете навалом). Какие же вы программеры если даже алгоритмы не изучаете?

Объясняю, но возму к примеру три камня (на 20 камней переделать очень легко):

1) У нас есть 3 камня.
Построим двоичное число:
000 - в котором количество цифр равно количеству камней (в нашем случае их три);

2) Затем к этому числу будем прибавлять единицу, а результат записывать, а потом опять к нему будем прибалять единицу, пока все цифры числа не будут являться единицами:
000+001= 001;
001+001= 010;
010+001= 011;
011+001= 100;
100+001= 101;
101+001= 110;
110+001= 111;

3) Таким образом, мы вместе с начальным число ( 000)получили все выборки нашего перебора:
000 001 010 011 100 101 110 111

4) Теперь проверяем массу камней в каждой выборке, учитывая, что цифра 0 - означает, что камень лежит в первой куче, а цифра 1 - во второй.

5) Все!

З.Ы. Вывод: Учи алгоритмы!!!

← →
Palladin © (2004-02-05 07:25) [6]

Алгоритмы не учат, если их учить от них не будет толка.

http://delphibase.endimus.com/?action=viewtopic&topic=mathalg

См. ветку про то, как раскидать числа по массивам, "чтобы разность сумм была минимальной."

Перебор! Найти похожие ветки