我需要一种总是能找到最佳解决方案的首次拟合递减bin装箱算法的替代方案

Asked
Viewd2372

-1

我已经实现了先验递减的装箱算法,将一个数字列表分成两个大小相等的“箱”。该算法几乎总能找到最佳的包装安排,但有时却找不到。

例如:

数字4、3、2、4、3、2的集合显然可以划分为以下排列: 1)4,3,2 2)4,3,2

第一个减少拟合的算法找不到解决方案。

在这种情况下,如果找不到正确的解决方案,那是不可接受的。

最初的难题是将数字序列分成两组,它们的总和相等。

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

1 个答案

2

装箱完成NP。

在这种情况下,如果找不到正确的解决方案,那是不可接受的。

尝试使用 Branch and Bound 算法,但是像所有精确算法一样,它不会扩展到中等或较大的问题。

先验拟合递减是一个很好的开始确定性算法,但是通过与元启发式(例如 Simulated Annealing Tabu搜索遗传算法。有几个开源库可以为您做到这一点,例如 Drools Planner (java)。