The Subset Sum Problem (SSP) is: ‘Given n positive integers w1, ..., wn, find a combination amongst them such that their sum is the closest to, but not exceeding, a positive integer c’. The most efficient algorithms which exactly solve the SSP have a pre-processing phase where the critical item and weight are necessary to be found. We introduce a new definition and algorithm for this pre-processing phase and it is also shown that the resulting approach induces, in the mean computational case, a traceable indices set with very few differences from the optimal solution.
