Techniques for solving subset sum problems within a given tolerance

The subset sum problem is a simple and fundamental NP-hard problem that is found in many real world applications. For the particular application motivating this paper (combination weighers) a solution is required to the subset sum problem that is within a small tolerance level, and can be computed quickly. We propose four techniques for solving this problem. The first two techniques are based on an efficient number partitioning algorithm. These techniques can solve small problems very efficiently when the solution uses approximately half the available items. The next technique is an enumeration technique that is capable of solving small problems very efficiently. The last technique is a modified enumeration technique that improves a good solution in a structured manner. These techniques were found to perform efficiently on large and small problems and can outperform other techniques currently proposed in the literature under certain conditions.