|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 17 Oct 2001 11:16:51
To : Martynenko Sergey
Subject : Re: задачка
--------------------------------------------------------------------------------
Martynenko Sergey wrote:
>
> > Из непереборных алгоритмов можно предложить только что-нибудь жадное,
> > эвристическое и приближенное. Hапример: берем два самых тяжелых слитка и
> > кладем в разные кучи. Затем берем два самых тяжелых из оставшихся и
> > кладем их в разные кучи так, чтобы минимизировать разницу. И т.д. Если
> > количество слитков нечетное, то последний слиток идет в кучу меньшего
> > веса.
>
> небольшое замечание :
Это не замечание. Это другой алгоритм.
> 1. сортируем по весу
> 2. пока исходная(отсортированная) куча не пуста, очередной ложим в кучу
> меньшую по весу
>
> тут если слиток будет весом больше, чем несколько последующих,
> докладываем меньшую кучу,
> брать всегда по два -> более плохой результат получится, при примерно
> той же сложности алгоритма
Да, конечно, такой вариант лучше. Мне почему-то захотелось сделать
количество слитков в кучах [примерно] одинаковым.
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
