Problem 44787. What can you get for exactly amount of money(harder)
Inspired by "Problem 42996. what can you get for exactly amount of money" https://ww2.mathworks.cn/matlabcentral/cody/problems/42996whatcanyougetforexactlyamountofmoney Problem 42996 is a good problem, but the test suit is too weak.
You go to store, where each product has price. Prices are in vector
v = [ 195 125 260 440 395 290] and you have amount of money s=570
Question is what can you buy, if you want to use whole amount of money
For this data answer is
res=[ 125 125 125 195]
The answer may not be unique, return any feasible answer. Do not cheat please.
In this hard version, 1 <= length(v) <= 50 1 <= s <= 10000000019 (1e10 + 19)
Solution Stats
Problem Comments

5 Comments
Because memory, some solution will not be allowed.
This problem merely requires a fast search heuristic that works only for the given test cases but not necessarily for the general case. For instance, the accepted solutions here will not pass for v = (1:50)+1e8 and s = 1e10+19. Also, the memory limit would be exceeded for v = 1:50 and s = 1e10+19.
The tip here is that numbers must be the same order of magnitude. For instance, if I have to add the integers 6 and 4 until they add to 1e20, it will take forever. However, the numbers 6e19 and 4e19 (multiples of 6 and 4) will find the sum 1e20 with one iteration.
And, I don't agree with Karl, my code finds a solution for v=1:50 and s=1e10+19 within 4 seconds. And for v = 1:50+1e8 within 12 seconds (at an i53230M CPU @ 2.60GHz). I am not sure there is a solution for (1:50)+1e8. It seems unlikely since 19 will be hard to appear from a magnitude of 1e8 within the range of s=1e10+19. In order words, we are trying to find the prime number 10000000019, and the smallest number that we are adding is 100000001 from (1:50)+1e8. If we add 100000001 one hundred times, the smallest number with the same order of 10000000019 is 10000000100.
Apparently, my solution worked faster when I sorted the vector "v" in descending order before doing anything else. Thanks Rafael S.T. Vieira. Now, I can find a solution for v=1:50 and s=1e10+19 within a few seconds as well.
Solution Comments
Show commentsProblem Recent Solvers12
Suggested Problems

4177 Solvers

1863 Solvers

Project Euler: Problem 2, Sum of even Fibonacci
2209 Solvers

66 Solvers

323 Solvers
More from this Author4
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!