当前位置：文江博客话题详情

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

发布于 2024-09-14 16:41:30 字数 125 浏览 4 评论 0原文

我不想优化任何东西，而是想列出所有可能的——包括“不完整的”——背包的包装。当然，我可以循环遍历对象集的所有子集，并选择满足权重约束的子集（可以通过在要查看的子集的大小上设置上限来改进），但我真的想要更多高效的。

谢谢。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

小苏打饼 2024-09-21 16:41:30

首先按重量对物品进行分类。然后递归打包背包。如果尚未考虑的最小重量物体不适合，或者我们没有剩余物体，则将当前背包添加到我们的列表中并返回，否则将当前背包添加到我们的列表中，对于列表中适合的每个物体将其放入并尝试将背包的其余部分装入比我们最后打包的物体更重的物体。

如果我们可以打包多个给定类型的项目，则将小于替换为小于或等于。

如果我们有多个相同重量的物体，我们需要首先按重量排序，然后按任意顺序排序，然后使用它。

 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)

First sort your objects by weight. Then recursively pack the knapsack. If the smallest weight object not yet considered does not fit, or we have no objects remaining, then add the current knapsack to our list and return, else add the current knapsack to our list for each object in the list that fits put it in and try to pack the rest of the knapsack with objects heavier than the last object we packed.

If we can pack more than one item of a given type then replace less than with less than or equal to.

If we have multiple objects of the same weight we need to sort first by weight, then by some arbitrary order, and use that.

 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)

回复收藏 0 原文

~没有更多了~