Форум: "Основная";
Текущий архив: 2004.02.13;
Скачать: [xml.tar.bz2];
Вниз
Перебор! Найти похожие ветки
← →
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]Алгоритмы не учат, если их учить от них не будет толка.
← →
Johnmen (2004-02-05 09:09) [7]http://delphibase.endimus.com/?action=viewtopic&topic=mathalg
← →
pasha_golub (2004-02-05 11:11) [8]dr Tr0jan © (05.02.04 04:18) [5]
Описаний в инете навалом.
Мозги должны быть, а не инет, Мастерок! :-)
← →
TUser (2004-02-05 11:27) [9]См. ветку про то, как раскидать числа по массивам, "чтобы разность сумм была минимальной."
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2004.02.13;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.012 c