Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 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
1-38797
uu
2004-02-03 12:40
2004.02.13
Разряд


1-38914
FMichael
2004-02-04 14:23
2004.02.13
Перемешение курсора в ActiveX Form


1-38796
GrayFace
2004-02-03 13:37
2004.02.13
Несовместимость с прошлыми версиями. DsgnIntf.pas, proxies.pas


1-38877
Maxim Vetera
2004-02-03 10:15
2004.02.13
Экраная лупа


9-38663
clim
2003-07-30 01:19
2004.02.13
Phyzics programming





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский