0

何かを最適化するのではなく、ナップザックの可能なすべてのパッキング (「不完全な」パッキングを含む) をリストしたいと思います。もちろん、オブジェクトのセットのすべてのサブセットをループして、重みの制約を満たすものを選択することもできます (サブセットのサイズに上限を設定することで改善できます)。効率的。

ありがとう。

4

1 に答える 1

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)
于 2010-08-12T11:12:34.847 に答える