有界背包问题设置。旺旺：所有可能的包装清单

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)