An efficient algorithm for the subset sum problem based on finite-time convergent recurrent neural network

For a given set S of n   real numbers, there are totally 2n−12n−1 different subsets excluding the empty set. The subset sum problem is defined as finding L subsets whose summation of subset elements are the L smallest among all possible subsets. This problem has many applications in operations research and real world. However, the problem is very computationally challenging. In this paper, a novel algorithm is proposed to solve this problem. Firstly, the L smallest k-subsets sum problem, a special case and sub-problem of the subset sum problem, is investigated. Given a positive integer k  (k≤n)(k≤n), k-subset means the subset of k distinct elements of S  . Obviously, there are totally (nk)k-subsets. By expressing all these k-subsets with a network, the L smallest k-subsets sum problem is converted to finding L shortest loopless paths in this network. By combining the L shortest paths algorithm and the finite-time convergent recurrent neural network, a new algorithm for the L smallest k-subsets sum problem is developed. Finally, the solution to the subset sum problem is obtained by combining the solutions to these sub-problems. And experimental results show that the proposed algorithm is very effective and efficient.