I need an alternative to the first fit decreasing bin packing algorithm that always finds an optimal solution

Question

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?

Answer 1

Bin packing is NP complete.

It is not acceptable in this circumstance to NOT find the correct solution if one exists.

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).