algorithm - 有界背包问题设置。想要 : a list of all possible packings

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)