Is there an algorithm which will tell me if the input number is a combination of the given array.The numbers in the array can be used n number of times Ex:- given array:-(1, 5, 7 and 10) input:- 17( yes since 10x1 +7x1) 65( yes since 10x6 + 5x1).. Here 10 is used 6 times. output:-2 7
Asked
Active
Viewed 99 times
1
-
2*65( yes since 6x10 + 5x1)* I keep rubbing my aged eyes but can't see the `6` in the given array. – High Performance Mark Aug 07 '15 at 15:21
-
possible duplicate of [Code Golf: Countdown Number Game](http://stackoverflow.com/questions/4586814/code-golf-countdown-number-game) – High Performance Mark Aug 07 '15 at 15:22
-
Please add more details i.e. is it allowed to use a number more than once, is parenthesis allowed? Also there is no 6 in your array. – xashru Aug 07 '15 at 15:30
-
1@xashru yes, The number can be used n number of times, 10 is multiplied 6 times – Aniket Aug 07 '15 at 15:32
-
1isn't it knapsack problem? – fex Aug 07 '15 at 16:15
-
The answers might be interesting but problem seems a tad incompletely stated. What are all the rules, precisely ? Because so far indeed that's a knapsack problem. Seems to be solvable by linear programming. – Mathias Dolidon Aug 07 '15 at 16:36
1 Answers
0
If you are allowed to use any number in the array any number of times, then there is an easy algorithm (but not the best one) and I am just going to describe the algorithm.
For a given number M, use the largest number in the array as many times as possible first. If k is the largest number, then find an n such that k*n <= M and k*(n+1) > M. Then use the second largest number in the array to fill in the gap between k*n and M and so on.
Example: if your array is [1, 5, 7, 10] and M=138, then use 10 (which is the largest number in the array) as many times as possible to get as closely to M without going over. In this case it's 13 times because 10*13 = 130 < M = 138 and 10*14 > 140 > 138 = M. Then use the second largest number, 7, to fill in the missing piece which is 8 (138-130). Then, obviously try to use 5 (which doesn't work), and finally use 1. So you get 1+7+10*13 = 138.
The above algorithm is not guaranteed to work though. If our array was [5, 7, 10], then the algorithm is not going to find a solution, if one exists.
under_the_sea_salad
- 1,754
- 3
- 22
- 42