Mark and toys

<p><strong>There are a number of toys</strong> lying in from of him, <strong>tagged with their prices</strong>. Mark has an only a <strong>certain amount to spend</strong>, and he wants <strong>to maximize</strong> the number of toys he buys with his money. Given a list of toy prices and a amount to spend, determine the maximum number of gift he can buys. <strong>Each toy can only be purchased once</strong>.</p> <h1>Considerations</h1> <ol> <li>There are a number of toys tagged with their prices. It means we have an slice <code>[1 4 7 3 4 9]</code> .</li> <li>Certain amount to spend, <code>7</code> . It means we have a target.</li> <li>Maximize the number of toys he can buy.</li> </ol> <h2>Combinatorial problems?</h2> <blockquote> <p><a href="https://www.fib.upc.edu/en/studies/masters/master-innovation-and-research-informatics/curriculum/syllabus/CPS-MIRI" rel="noopener ugc nofollow" target="_blank">A combinatorial</a> problem consists in, given a finite collection of objects and a set of constraints, finding an object of the collection that satisfies all constraints</p> </blockquote> <p>Let rephrase the problem to something like this:</p> <ol> <li>Find all combinations in an slice that are equal or less than a target.</li> <li>Then, choice the largest one. And return their size</li> </ol> <p>But do we care about the combinations? do we need to find them all?. The truth is that, <strong>it would be a waste of effort</strong>. Leading to an unnecessary increasing complexity and and extrange solutions.</p> <h2>A little more Thinking</h2> <p>What we really need is to <strong>find the largest combination</strong> and <strong>return their size</strong>. My original thinking was wrong I couldn’t build a solution that was easy to reason about and satisfy all the requirements.</p> <h2>Greedy algorithms</h2> <p>Greedy is an algorithm paradigm that build up a solution piece by piece, always choosing the next piece that offers the most obvios and immediate benefits. So the problems where choosing locally optimal also leads to global solution are the best fit for greedy.</p> <h2>Characteristics of Greedy algorithm</h2> <ul> <li>There must be <strong>an ordered list</strong> of resources</li> <li>Maximum of all the resources are taken</li> </ul> <p>It is called greedy because it tries to find the solution by making the best choice at each stage, without considering the future steps or the consequences of the current decision.</p> <p><a href="https://luillyfe.medium.com/mark-and-toys-95879d25dd1">Read More</a></p>