Ограниченный набор проблем knaxack. Хотите: список всех возможных упаковок

Question

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

Спасибо.

Answer 1

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

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

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

 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)