|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Smirnov 2:5020/2115.110 07 May 2002 01:58:37
To : Dmitry Zhadanoff
Subject : опять рюкзак
--------------------------------------------------------------------------------
DZ> А задача такая - есть рюкзак объемом float(любой real). Есть куча
DZ> предметов массой тоже float. Hеобходимо набить рюкзак под завязку.
DZ> Лучше - несколько наиболее подходящих вариантов загрузки. Объясните
DZ> пожалуйста на пальцах (именно на пальцах) возможный алгоритм решения
DZ> задачи.
Один из вариантов решения - дерево, узел - комбинация из упакованных и
отброшенных грузов. Строится следующим образом:
Корень - это пустой рюкзак. Дальше две ветки - левая это положили первый груз,
правая - ничего не положили (опять пустой рюкзак). Имеем два варианта (корень не
считаем). Теперь для каждого листа - опять по две ситуации, левое поддерево
положили _второй_ груз, правое - не положили. Имеем 4 варианта. Потом третий
груз. И т.д. В конце концов попытавшись добавить очередной узел, обнаруживаем
переполнение по объему, все, по этой ветке вариантов больше нет. Если общий
объем грузов значительно больше объема рюкзака то имеем хороший выигрыш за счет
таких отсечений. Если грузы отсортировать по массе и начинать с самых тяжелых,
то можно делать еще отесечения по весу: когда масса всех оставшихся грузов плюс
масса текущего узла не больше чем достигнутый к этому моменту рекорд, то эту
ветку тоже можно отбросить. Hаконец отсортировав грузы по отношению масса/объем,
вместо предыдущего варианта, можно делать отсечения по плотности: (если
оставшийся объем рюкзака * плотность в текущем узле + вес узла) меньше рекорда
то для данного узла тоже прекращаем перебор.
Если нужно несколько вариантов, то запоминай не один рекордный узел, а список из
К узлов максимальных по массе.
Hа пальцах вроде так.
Пока, Dmitry! Увидимся там, где будет светло...
---
* Origin: Все животные равны, но некоторые равнее других. (2:5020/2115.110)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
