Задача с ограниченным ранцем.Хотите: список всех возможных упаковок - PullRequest
Новая
       33

Задача с ограниченным ранцем.Хотите: список всех возможных упаковок

0 голосов
/ 12 августа 2010

Вместо того, чтобы что-то оптимизировать, я хочу перечислить все возможные, включая «неполные», упаковки рюкзака.Конечно, я мог бы перебрать все подмножества набора объектов и выбрать те из них, которые удовлетворяют ограничению веса (можно улучшить, установив верхнюю границу для размера подмножеств для просмотра), но мне бы очень хотелось чего-то большегоэффективный.

Спасибо.

1 Ответ

1 голос
/ 12 августа 2010

Сначала отсортируйте ваши объекты по весу.Затем рекурсивно запакуйте рюкзак.Если наименьший весовой объект, который еще не рассматривался, не подходит, или у нас нет оставшихся объектов, то добавьте текущий рюкзак в наш список и верните его, в противном случае добавьте текущий рюкзак в наш список для каждого подходящего объекта, вставьте его ипопробуйте упаковать оставшуюся часть рюкзака с объектами, которые тяжелее, чем последний упакованный нами объект.

Если мы можем упаковать более одного предмета данного типа, замените его менее чем на меньшее или равное.

Если у нас есть несколько объектов одинакового веса, нам нужно сначала отсортировать их по весу, а затем по произвольному порядку и использовать их. 

 PackKnapsack(knapsack, objects)
   add knapsack to list
   if objects is empty return
   if smallest object does not fit return
   for each object in order from smallest to largest
      if currentobject does not fit
         break
      PackKnapsack(knapsack + currentObject, objects heavier than current object)
...