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

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items...

Answer 2

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 3

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 ≤ includeItemi ≤ 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.