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?1 2 n ? 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 ( n k ) 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.
subset sum problem recurrent neural network l smallest k-subsets sum problem l shortest paths convergence in finite time