algorithm - 我需要一个替代第一个适合减少装箱算法的方法，它总是找到一个最佳解决方案

Question

我已经实现了 First-Fit-Decreasing bin 打包算法，将数字列表拆分为两个大小相等的“bin”。该算法几乎总能找到最佳包装安排，但有时却找不到。

例如：

数字 4, 3, 2, 4, 3, 2 的集合显然可以拆分成这样的排列： 1) 4, 3, 2 2) 4, 3, 2

第一次拟合递减算法找不到解决方案。

在这种情况下，不找到正确的解决方案（如果存在）是不可接受的。

最初的难题是将一个数字序列分成两个总和相等的集合。

这只是一个简单的装箱问题还是我使用了错误的算法？

Answer 1

装箱是 NP 完全的。

在这种情况下，不找到正确的解决方案（如果存在）是不可接受的。

尝试分支定界算法，但与所有精确算法一样，它不适用于中型或大型问题。

First-Fit-Decreasing是一个很好的起始确定性算法，但您可以通过将其与元启发式方法（如Simulated Annealing、Tabu Search或Genetic Algorithms）链接起来做得更好。有几个开源库可以为您做到这一点，例如Drools Planner (java)。