# Knapsack Problem with weight equal to value, and sum can be smaller or equal than the target

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.

Examples:

1)

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

Target: 7000

Result: [2000,5000]

2)

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

Target: 7990

Result: [500, 2000, 5000]

3)

Given values: [222,333]

Target: 444

Result: [222,222]

4)

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.

• There are some pretty standard implementations of the Knapsack problem which are decently fast. Have you tried those> Oct 29, 2019 at 14:50
• 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. Oct 29, 2019 at 15:08
• 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. Oct 29, 2019 at 15:14