Bounded Knapsackの問題のセットアップ。欲しい：すべての可能なパッキングのリスト

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)