我需要一种替代第一个拟合递减装箱算法的方法，该算法总是能找到最佳解决方案
我已经实现了首次适应递减装箱算法，将数字列表拆分为两个大小相等的“箱子”。该算法几乎总能找到最佳的包装排列，但有时也找不到。
例如：
数字 4, 3, 2, 4, 3, 2 的集合显然可以分为这样的排列： 1) 4, 3, 2 2) 4, 3, 2
第一个拟合递减算法没有找到解。
在这种情况下，如果存在正确的解决方案，则找不到正确的解决方案是不可接受的。
最初的难题是将数字序列分成总和相等的两组。
这只是一个简单的装箱问题还是我使用了错误的算法？
I have implemented the First-Fit-Decreasing bin packing algorithm to split a list of numbers into two 'bins' of equal size. The algorithm almost always finds the optimal packing arrangement but occasionally it doesn't.
For example:
The set of numbers 4, 3, 2, 4, 3, 2 can obviously be split into this arrangement:
1) 4, 3, 2
2) 4, 3, 2
The first fit decreasing algorithm does not find a solution.
It is not acceptable in this circumstance to NOT find the correct solution if one exists.
The original puzzle is to split a sequence of numbers into two sets that have an equal sum.
Is this just a simple bin packing problem or have I used the wrong algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
装箱是 NP 完全的。
尝试分支定界算法，但与所有精确算法一样，它无法扩展到中型或大型问题。
First-Fit-Decreasing 是一个很好的起始确定性算法，但是您可以通过将其与元启发式（例如模拟退火）链接来做得更好、禁忌搜索或遗传算法。有几个开源库可以为您做到这一点，例如 Drools Planner (java).
Bin packing is NP complete.
Try the Branch and Bound algorithm, but like all the exact algorithms, it doesn't scale to medium or big problems.
First-Fit-Decreasing is a good starting deterministic algorithm, but you can do much better by chaining it with meta-heuristics such as Simulated Annealing, Tabu Search or Genetic Algorithms. There are a couple of open source libs out there which can do that for you, such as Drools Planner (java).