A packing algorithm … kind of

Question

Given an array of items, each of which has a value and cost, what's the best algorithm determine the items required to reach a minimum value at the minimum cost? eg:

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

Note that the overall value:cost ratio at the end is irrelevant (A + A would give you the best value for money, but A + B + B is a cheaper option which hits the minimum value).

Answer 1

This is the knapsack problem. (That is, the decision version of this problem is the same as the decision version of the knapsack problem, although the optimization version of the knapsack problem is usually stated differently.) It is NP-hard (which means no algorithm is known that is polynomial in the "size" -- number of bits -- in the input). But if your numbers are small (the largest "value" in the input, say; the costs don't matter), then there is a simple dynamic programming solution.

Let best[v] be the minimum cost to get a value of (exactly) v. Then you can calculate the values best[] for all v, by (initializing all best[v] to infinity and):

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

Then look at best[v] for values upto the minimum you want plus the largest value; the smallest of those will give you the cost.

If you want the actual items (and not just the minimum cost), you can either maintain some extra data, or just look through the array of best[]s and infer from it.

Answer 2

This problem is known as integer linear programming. It's NP-hard. However, for small problems like your example, it's trivial to make a quick few lines of code to simply brute force all the low combinations of purchase choices.

NP-harddoesn't mean impossible or even expensive, it means your problem becomes rapidly slower to solve with larger scale problems. In your case with just three items, you can solve this in mere microseconds.

For the exact question of what's the best algorithm in general.. there are entire textbooks on it. A good start is good old Wikipedia.

Answer 3

Edit This answer is redacted on account of being factually incorrect. Following the advice in this will only cause you harm.

This is not actually the knapsack problem, because it assumes that you cannot pack more items than there is space for in some container. In you case you want to find the cheapest combination that will fill up the space, allowing for the fact that overflow may occur.

My solution, which I don't know is the optimal but it should be pretty close, would be to compute for each item the cost benefit ratio, find the item with the highest cost benefit and fill the structure with this item until there isn't space for one more item. Then I would test to see if there was a combination with any of the other available items that could fill the available slot for less that the cost of one of the cheapest items and then if such a solution exist, use that combination otherwise use one more of the cheapest items.

Amenddum This may actually also be NP-complete, but I am not sure yet. Anyway for all practical purposes this variation should be much faster than the naive solution.