Problem 44787. What can you get for exactly amount of money(harder)

Created by li haitao

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Inspired by \"Problem 42996. what can you get for exactly amount of money\"</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://ww2.mathworks.cn/matlabcentral/cody/problems/42996-what-can-you-get-for-exactly-amount-of-money\"><w:r><w:t>&lt;https://ww2.mathworks.cn/matlabcentral/cody/problems/42996-what-can-you-get-for-exactly-amount-of-money</w:t></w:r></w:hyperlink><w:r><w:t>&gt; Problem 42996 is a good problem, but the test suit is too weak.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You go to store, where each product has price. Prices are in vector</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>v = [ 195 125 260 440 395 290] and you have amount of money s=570</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Question is what can you buy, if you want to use whole amount of money</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For this data answer is</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>res=[ 125 125 125 195]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The answer may not be unique, return any feasible answer. Do not cheat please.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>In this hard version, 1 &lt;= length(v) &lt;= 50 1 &lt;= s &lt;= 10000000019 (1e10 + 19)</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

31 Solutions
9 Solvers

Last Solution submitted on Jun 17, 2022

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Binbin Qi on 21 Nov 2018

Because memory, some solution will not be allowed.

Karl Ezra Pilario on 4 Jun 2020

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.

Rafael S.T. Vieira on 22 Jul 2020

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.

Rafael S.T. Vieira on 22 Jul 2020

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.

Karl Ezra Pilario on 28 Jan 2021

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.

Problem Recent Solvers9

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 44787. What can you get for exactly amount of money(harder)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author4

Problem Tags

Community Treasure Hunt

Problem 44787. What can you get for exactly amount of money(harder)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers9

Suggested Problems

More from this Author4

Problem Tags

Community Treasure Hunt

Players