Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Не знаю классических решений 01.11.01 13:12 Число просмотров: 2031
Автор: PS <PS> Статус: Elderman
|
просто хочу предложить то, что пришло в голову.
Итак есть:
1. L - кол-во куч
2. wi - коэфициент (вес) iой монеты.
3. V=vi...vL массив заданый пользователем
4. Tij = vi/vj, где j=i+1
5. Wi - вес кучи = Sum w
6. Dij = Wi/Wj, где j=i+1
1. Выбераем базу B состоящую из монет наибольшего w.Bпока менять не будем.
1.1 Случайным образом распределим оставшиеся монеты по кучам.
1.2 Проверим условие выполнения задачи
1.3 Найдем MAX Dij и MIN Dmn
1.4 Переместим монету с MIN w из кучи i в кучу m.
1.5 Перейдем на 1.2
Может получиться, что после 1.4 Dij станет минимальной, а Dmn-максимальной. Т.е. вечный цикл. На вскидку пути решения: 1. Перейти к п1.1, или не трогать Dij и Dmn, а распределять для других куч.
2. Если вBвсе w равны - закончить. Если нет,то:
2.1 переставить кучи так, что бы базовые элементы с разным w оказались на других местах.
2.2 повторить алгоритм с п1.1
2.3 Повторить п2.1 пока не переберутся все возможные варианты вB
2.4 Выбрать оптимальный.
Т.е. это что-то типа множества весов( две чашки на палке :) ), которые необходимо сбалансировать.
Ногами не пинать, придумал за 10минут :)))
> Извиняюсь за offtipic, но в programming только всякая
>ерунда
>
> Помните задачку из учебников/олимпиад когда надо
> минимальным количеством монет набрать нужную сумму. На
> первый взгляд в том-же духе...
>
> Так вот (по взрослому):
> 1) имеем толстый кошелек с монетами, при этом для каждой
> монеты задан ее возраст (коэффициент новизны);
> 2) пользователем задан массив вещественных коэффициентов;
> 3) нужно разложить монеты в кучки (по количеству заданных
> коэффициентов), так чтобы суммы в кучках относились между
> собой также как и коэффициенты в массиве, с минимальной
> ошибкой;
> 4) при раскладке монет нужно очень постараться разложить их
> так, чтобы в каждой кучке было хотя бы по одной «новой»
> монете. Другими словами если у нас пять кучек, то по одной
> из пяти самых новых монет должно лежать в каждой кучке;
>
> Мне нужно было сделать быстро, за день-два (вместе с
> «прикладной» частью), поэтому я сделал «в лоб» перебором с
> «кружевами». Но вот может кто из обладателей классического
> образования, что-нибудь толковое скажет :-)
>
> Известные мне алгоритмы ломаются на том, что нужно найти
> именно оптимальное решение для нескольких сумм, а не просто
> "подобрать монеты".
>
> Задача не придумана, а является реальной (распределение
> ресурсов).
>
> Ну и как-бы совсем offtopic (еще раз прошу прощенья):
> Я работу ищу (в Москве), программирование всякое, а-ля
> драйвера для W2K/XP/Linux, и НЕ генераторы отчетов. Может
> кто что посоветует. Резюме есть на
> http://leo-yuriev.narod.ru
>
> Удачи.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
