Polynomial approximation of the subset-sum problem
npm install subset-sumPolynomial approximation of the subset-sum problem.
For the given t integer and arr set of integers, the algorithm computes the closest possible sum to t from a subset of arr (the result is equal or less that t). Example: arr=[2, 3, 10], t=14, the closest sum is 13, since 10+3=13.
The subset-sum problem is NP-hard, so computing the exact solution takes exponential time.
This module uses a polynomial approximation algorithm, that allows you to fine-tune the error/time-complexity ratio.
``
$ npm install subset-sum
`js`
var approx = require('subset-sum');
Return the closest sum to t (lesser or equal) that can be computed from a subset of arr.
With eps = 0 the algorithm has exponential time, but it is accurate.eps > 0
With the computation has polynomial complexity, but the result may have error up to epst (so a closer sum to t may* exist).
eps can be arbitrary small, but as eps goes to 0, the complexity becomes exponential.
`js`
console.log(approx([2,3,4,5,10,11,13,16,22,28,30], 97)); // eps = 0, the solution is accurate (97)
console.log(approx([2,3,4,5,10,11,13,16,22,28,30], 97, 0.5)); // eps = 0.5, the solution has error (94)
See benchmark.js`
MIT