Packing algorithm ... view
Given an array of elements, each with value
and cost
, what is the best algorithm to determine the elements needed to achieve the 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: the cost ratio at the end does not matter ( A + A
will give you the best value for money, but A + B + B
a cheaper option that hits the minimum).
source to share
This is a backpack problem. (That is, the version of the solution to this problem is the same as the version of the solution to the knapsack problem, although the optimization version of the knapsack problem is usually specified differently.) This is NP-hard (which means that the algorithm does not know what the polynomial is in "size "- the number of bits - at the input). But if your numbers are small (the biggest "value" in the input, say the cost doesn't matter) then there is a simple dynamic programming solution.
Best for [v] to be the minimum cost to get the value of (exactly) v. Then you can calculate the best [] values 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 up to the minimum value you want plus the largest value; the smallest one will give you value.
If you want the actual items (not just the minimum cost), you can either save some extra data or just look at the best [] s array and infer from it.
source to share
Edit This answer has been edited because it is actually incorrect. By following the advice in this case, you are hurting you.
This is not a problem with a backpack because it is assumed that you cannot pack more items than in any container. In this case, you want to find the cheapest combination that will fill the space, allowing for overflow.
My solution, which I don't know, is optimal, but it should be pretty close, it would be to calculate the cost-benefit ratio for each item, find the item with the highest cost and fill the structure with that item until there is no room for another item. ... Then I would check if there is a combination with any of the other available items that could fill the available slot for less than the cost of one of the cheapest items, and then if such a solution exists, use that combination, otherwise use another one of the cheapest goods.
Amenddum This may also be NP-complete, but I'm not sure yet. Anyway, for all practical purposes this option should be much faster than the naive solution.
source to share
This problem is known as integer linear programming. It's NP-hard. However, for small problems like your example, it is trivial to make a few short lines of code to just translate all the low buy option combinations.
NP-harddoes doesn't mean impossible or even costly, it means that your problem becomes slower to solve with larger problems. In your case, there are only three elements, you can solve it in a few microseconds.
There are whole tutorials on it for the exact question of which is the best algorithm in general. A good start is the old old Wikipedia.
source to share