опять рюкзак

From

Sergey Smirnov (2:5020/2115.110)

To

Dmitry Zhadanoff

Date

2002-05-07T01:58:37Z

Area

RU.ALGORITHMS

░▒▓WIN98 01:40 - самое время написать в RU.ALGORITHMS
         Большой брат видит тебя, Dmitry!

 DZ>     А задача такая - есть рюкзак объемом float(любой real). Есть куча
 DZ> предметов массой тоже float. Необходимо набить рюкзак под завязку.
 DZ> Лучше - несколько наиболее подходящих вариантов загрузки. Объясните
 DZ> пожалуйста на пальцах (именно на пальцах) возможный алгоритм решения
 DZ> задачи.

Один из вариантов решения  - дерево, узел - комбинация из упакованных и отброшенных грузов. Строится следующим образом:

Корень - это пустой рюкзак. Дальше две ветки - левая это положили первый груз, правая - ничего не положили (опять пустой рюкзак). Имеем два варианта (корень не считаем). Теперь для каждого листа - опять по две ситуации, левое поддерево положили _второй_ груз, правое - не положили. Имеем 4 варианта. Потом третий груз. И т.д. В конце концов попытавшись добавить очередной узел, обнаруживаем переполнение по объему, все, по этой ветке вариантов больше нет. Если общий объем грузов значительно больше объема рюкзака то имеем хороший выигрыш за счет таких отсечений. Если грузы отсортировать по массе и начинать с самых тяжелых, то можно делать еще отесечения по весу: когда масса всех оставшихся грузов плюс масса текущего узла не больше чем достигнутый к этому моменту рекорд, то эту ветку тоже можно отбросить. Наконец отсортировав грузы по отношению масса/объем, вместо предыдущего варианта, можно делать отсечения по плотности: (если оставшийся объем рюкзака * плотность в текущем узле + вес узла) меньше рекорда то для данного узла тоже прекращаем перебор.

Если нужно несколько вариантов, то запоминай не один рекордный узел, а список из К узлов максимальных по массе.

На пальцах вроде так.

Пока, Dmitry! Увидимся там, где будет светло...


---
 * Origin: Все животные равны, но некоторые равнее других. (2:5020/2115.110)