Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed
-
06-11-2019 - |
题
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.
没有正确的解决方案