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/42996-what-can-you-get-for-exactly-amount-of-money 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 i5-3230M 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
-
2037 Solvers
-
"Low : High - Low : High - Turn around " -- Create a subindices vector
532 Solvers
-
1405 Solvers
-
Hexagonal numbers on a spiral matrix
136 Solvers
-
320 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!