Find the best combination of items, for the lowest cost. Maybe a knapsack variant?

Question

The Story

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

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

1000 for $300 ($.3 per bean) 750 for $225 ($.3 per bean) 600 for $180 ($.3 per bean)

300 for $150 ($.5 per bean) 250 for $125 ($.5 per bean) 100 for $50 ($.5 per bean)

10 for $10 ($1 per bean) 5 for $5 ($1 per bean) 1 for $1 ($1 per bean)

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.

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. I want to buy the combination of bags that will give me at least N beans, for the lowest possible price.

What Am I trying to do?

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.

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.

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.

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

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.

What I think my Code will do

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.

The Question

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"

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

Thanks!

Answer 1

Yes, this falls into a loose interpretation of the Knapsack region.

Details

First of all, use dynamic programming: save the results from each call in an array. Never compute that value a second time.

Your basic cut-off point is when you try to buy a sack that would combine with others already in the solution, to equal the count of a larger sack. Bail on the solution there; a higher branch will find the larger sack for you.

Note that this applies to combining solutions: check after each return. For instance, if you're down to 7 beans, your call will return (5, 1, 1). If you already have a 5-bean bag in the higher solution, abandon that branch -- a higher branch will (or has) found the 10-bean solution.

Higher Processing

You can build a list of short-cuts if you determine the basic combinations in advance: three 100-bean bags make a 300, etc. This allows you to proactively limit the quantity of 100-bean bags in any solution path. However, this doesn't help much in a general, chaotic environment, where most quantities don't divide another. I wouldn't bother with mixed combinations, as testing for a multiple match on each return will complicate your code with little return.

Testing

Make sure you try some cases where the largest bag and some small ones are more expensive than a combo of medium bags.

Try some weird cases: powers of 2, Fibonacci amounts, prime numbers, etc.