algorithm - 有界背包问题设置。想要：所有可能的包装清单

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)