ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Leo                                  2:5020/400     01 Nov 2001  17:52:05
 To : All
 Subject : "Взрослая" задача о монетах, нужен алгоритм
 -------------------------------------------------------------------------------- 
 

 Hi All!
 
 Помните задачку из учебников/олимпиад когда надо минимальным количеством монет
 набрать нужную сумму. Hа первый взгляд в том-же духе... 
 
 Так вот (по взрослому): 
 1) имеем толстый кошелек с монетами, при этом для каждой монеты задан ее
 возраст (коэффициент новизны); 
 2) пользователем задан массив вещественных коэффициентов; 
 3) нужно разложить монеты в кучки (по количеству заданных коэффициентов), так
 чтобы суммы в кучках относились между собой также как и коэффициенты в
 массиве, с минимальной ошибкой; 
 4) при раскладке монет нужно очень постараться разложить их так, чтобы в
 каждой кучке было хотя бы по одной 'новой' монете. Другими словами если у нас
 пять кучек, то по одной из пяти самых новых монет должно лежать в каждой
 кучке; 
 
 Задача не придумана, а является пересказанной реальной (распределение
 ресурсов). 
 
 Мне нужно было сделать быстро, за день-два (вместе с "прикладной" частью),
 поэтому я сделал "в лоб" перебором с "кружевами". Hо вот может кто из
 обладателей классического образования, что-нибудь толковое скажет :-) 
 
 Известные мне алгоритмы ломаются на том, что нужно найти именно оптимальное
 решение для нескольких сумм, а не просто "подобрать монеты". 
 
 Hу и как-бы offtopic (прошу прощенья): 
 Я работу ищу (в Москве), программирование всякое, а-ля драйвера для
 W2K/XP/Linux, и HЕ генераторы отчетов. Может кто что посоветует. Резюме есть
 на http://leo-yuriev.narod.ru 
 
 Удачи. 
 
 Lea (aka OS)
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор