Find the best combination of items, for the lowest cost. Maybe a knapsack variant?
<h1><strong>The Story</strong></h1>

<p>I want to make my grandmothers famous N-bean soup. The recipe calls for exactly N beans.</p>

<p>The grocery store only sells beans in prepackaged bags. Each bag contains a specific number of beans, for a different price.</p>

<p><code>1000 for $300 ($.3 per bean)
750 for $225 ($.3 per bean)
600 for $180 ($.3 per bean)</code></p>

<p><code>300 for $150 ($.5 per bean)
250 for $125 ($.5 per bean)
100 for $50 ($.5 per bean)</code></p>

<p><code>10 for $10 ($1 per bean)
5 for $5 ($1 per bean)
1 for $1 ($1 per bean)</code></p>

<p>A federal grocery law states that a larger bag of beans will never have a a more expensive per-bean cost than a smaller bag, but it can be equal. In short, The more beans in a bag, the better the value.</p>

<p>When I go to the store, I need to make sure I buy AT LEAST N beans for the recipe. I also want to spend as little money as possible. I don't care if I buy more beans than I need for the recipe, I just want to make sure I get the very best deal to do so. <strong>I want to buy the combination of bags that will give me at least N beans, for the lowest possible price.</strong></p>

<h1><strong>What Am I trying to do?</strong></h1>

<p>I'm trying to write an algorithm that will calculate this rather quickly. I unfortunately need to call it quite often in the game I am writing, where you can drag a value slider to change the amount of Beans required for the recipe.</p>

<p>This problem is very close to the Knapsack problem, or the Making Change problem, but different, because I don't care about the number of items I take, and I care about the total cost instead. I think that Dynamic Programming is the way to go, but I don't really understand enough about it to start breaking down the problem into smaller chunks.</p>

<p>Here's what I'm currently thinking: I want to write a function that creates a set of possible Bean Bag Purchases. I want to evaluate the high quantity (highest value) bags first. I have to go top down, because going bottom up, because of the federal law, will create low value results, that I know will be more expensive.</p>

<p>I want to create a function that branches at every bag purchase, and calculates what would happen if I Did, or Did Not buy one more of a particular bag, and then continues calculating. It starts with the most expensive bags, and goes progressively lower</p>

<p>I think that I should be storing these possible combinations as a 2 dimensional array, where the "columns" are the number of bags you buy, and each row represents a complete combination of bags to reach the target number of beans. After calculating the possible valid transactions, I can chew through the 2D array, and find the one with the lowest total cost, and if several of those are equal, I select the one with the least number of bags bought total.</p>

<h1><strong>What I think my Code will do</strong></h1>

<p>For example, Lets say my recipe calls for 1602 beans. I first buy 2x1000 count bags, for a total of $600. That's a valid purchase, but maybe not the best deal. Buying a 3rd 1000 count bag would be invalid, so I instead branch, and buy only 1x1000 count bag, and 1x750 count, for a total of 525. A Better deal! I then branch again, and buy 1x1000 + 2x600 = $660, which is worse. Branch again: 1x1000 + 1x600 + 1x300 = $630. And so on, until I reach 1x1000 + 1x600 + 2x1 for $482. This is the best deal possible, but I don't know that yet, I have to chew through the next branching point.</p>

<h1>The Question</h1>

<p>My big problem is: I think I can write a recursive loop to go through and evaluate every single possible purchase. But how do I know when I can safely bail out of this loop early? At what point can I say with certainty "OK, that last branch proved to me that further calculations are not necessary, I have found the best deal that is available. Let's stop now, and save time"</p>

<p>Does this kind of problem have a name? Is it some kind of variant of the Knapsack Problem?</p>

<p>Thanks!</p>