I would like to find the sum of values from a given number array, where the repetition of numbers are allowed, closest to a target but the sum cannot exceed the target. If there are more solution, I'd prefer the one with the minimum element count.



Given values: [500, 1000, 2000, 5000]

Target: 7000

Result: [2000,5000]


Given values: [500, 1000, 2000, 5000]

Target: 7990

Result: [500, 2000, 5000]


Given values: [222,333]

Target: 444

Result: [222,222]


Given values: [222,333]

Target: 777

Result: [222,222,333]

Later on I would like to implement this algorithm in JavaScript, and make it run in a browser. I have tried:

  • Knapsack algorithm

  • Generating all combination of the numbers and find one with the minimum difference

but both are very slow when implemented, and used with big numbers.

  • $\begingroup$ There are some pretty standard implementations of the Knapsack problem which are decently fast. Have you tried those> $\endgroup$ – Don Thousand Oct 29 '19 at 14:50
  • $\begingroup$ Yes I have, but is is still too slow. Basically everything over 2 seconds is slow in my case. The problem is, that it is building such a huge matrix, that if it runs on a slower computer, is just crashes the browser. This is why I am interested in an optimized algorithm just for my case. $\endgroup$ – JuniorNinjaTurte Oct 29 '19 at 15:08
  • 1
    $\begingroup$ As you understand, the knapsack problem in its full generality calls for exhaustive search, and that will be slow. (Many algorithms are recursive, so don't need a "huge matrix" but are still slow.) If you hope to speed up the calculation for your particular problem you will have to specify the problem more carefully to show how it's less than fully general. Then perhaps ask at the theoretical cs site, or on stackoverflow. $\endgroup$ – Ethan Bolker Oct 29 '19 at 15:14

I have posted the question to CS Stackexchange as recommended, and a madman named Steven just answered it, so I will share it with you all, and close this thread.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.