algorithm to find best combination

Question

Assume that I have a list of 100 products, each of which has a price. Each one also has a energy (kJ) measurement.

Would it be possible to find the best combination of 15 products for under $10 of which the sum of the energy (kJ) was greatest, using programming?

I know C#, but any language is fine. Cheers.

Update: Having a bit of troble finding some sample source code for the knapsack issue. Does anyone have any or know where to find some. Been googling for a few hours and need to get this sorted by tomorrow if possible. Ta.

Answer 1

http://en.wikipedia.org/wiki/Knapsack_problem

Answer 2

That sounds a lot like the knapsack problem. There are various approaches (order descending by energy density, for example).

Answer 3

This reminds me of the famous knapsack algorithm

http://en.wikipedia.org/wiki/Knapsack_problem

Answer 4

This sounds more like a linear programming problem.

Informally, linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations.

Check out the Simplex Method.

Answer 5

This in Integer Linear Programming, optimizing a linear equation subject to linear constraints, where all the variables and coefficients are integers.

You want variables includeItem1, ..., includeItemN with constraints 0 ≤ includeItem*i* ≤ 1 for all values of i, and includeItem1 + ... + includeItemN ≤ 15, and includeItem1*priceItem1 + ... ≤ 10, maximizing includeItem1*kilojouleItem1 + ....

Stick that in your favorite integer linear program solver and get the solution :)

See also http://en.wikipedia.org/wiki/Linear_programming

It doesn't make sense to say that your particular problem is NP-complete, but it's an instance of an NP-complete (kind of) problem, so there might not be a theoretically fast way of doing it. Depending on how close to optimality you want to get and how fast ILP solvers work, it might be feasible in practice.

I don't think you problem is a special case of ILP that makes it particularly easy to solve. Viewing it as a knapsack-like problem, you could restrict yourself to looking at all the subsets of 1..100 which have at most (or exactly) 15 elements, which is polynomial in n---it's n-choose-15, which is less than (n^15)/(15!), but that's not terribly useful when n = 100.

If you want recommendations for solver programs, I have tried glpk and found it pleasant to use. In case you want something that costs money, my lecturer always talked about CPLEX as an example.

Answer 6

This is the knapsack problem if you can either pick a product or not. If you can pick fractional values of products then you could solve this with the simplex method, but the fractional knapsack problem has a simple solution.

Order the items by energy/price ratio, picking 100% of the highest ones until you run out of money, then pick a fractional value of the highest remaining one.

For example if prices are 4,3,5,4 and energies are 3,5,2,7 the ordering is

7/4, 5/3, 3/4, 2/5

So you would pick items 4 and 2 which would cost 7$, with the 3$ remaining you would buy 75% of the first item for a price of $3 and an energy of 3*.75 = 2.25

This would give a total energy of 14.25

Note that allowing fractional values will give you a higher objective value than only allowing 0% or 100%, so no integer solution will do any better than 14.25 (or 14 for that matter since the objective value has to be an integer).

To solve the original knapsack problem, you can use a branch-and-bound which should work just fine in practice. Assume that you have a current candidate solution with an objective value of z*

1. Solve the relaxed problem, where you allow the fractional weights. If the value is less than z*, discard this branch.
2. Compute a new value z which is the solution found without the last fractional weight, if this value is greater than z* , replace z* with your new value
3. Pick one item (say the first in the list, the most profitable one) and form two subproblems, one where you must include it in the solution and one where you cannot include it in the solution (this is the branching step).
4. As long as you have subproblems left to solve, pick one and go back to step 1.

Note that when you create the subproblem where you must pick an item, just subtract its price from the budget and add the value to the profit, now you have a smaller problem to solve.

For a more detailed description look at Branch and Bound on Wikipedia.

Answer 7

The Stony Brook Algorithm Repository lists implementations for the knapsack problem.

Their book The Algorithm Design Manual has this kind of information for a vast array of problems.

Answer 8

It should be possible to solve the problem with Cream for Java. There's also a version for C# available CSharpCream.

Answer 9

Yes, as everyone pointed out this is a complex knapsack problem. Something this simple might be good enough though...

SELECT TOP 15 *
FROM Product
WHERE Price < 10
ORDER BY Energy DESC