algorithm to find best combination

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.

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.

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

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.

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.

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 

This reminds me of the famous knapsack algorithm

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

Did something similar to this on a personal project, but in php code. If you wish to port to c#, feel free.

This code takes into account the possibility of multiple combinations being the same, so the return value will be an array of x best results.

NOTE: This is taking in to account that any item can be used 0 or 1 times in each result

<?php $products = [ ['id' => 1, 'price' => 3.00, 'energy' => 200], ['id' => 2, 'price' => 14.10, 'energy' => 3200], ['id' => 3, 'price' => 2.66, 'energy' => 300], ['id' => 4, 'price' => 5.00, 'energy' => 450], ['id' => 5, 'price' => 6.23, 'energy' => 667], ['id' => 6, 'price' => 7.00, 'energy' => 1200] ]; function genCombinations($values, $count = 0) { // Figure out how many combinations are possible: $comboCount = pow(count($values) , $count); $r = []; // Iterate and add to array for ($i = 0; $i < $comboCount; $i++){ $r[] = getCombination($values, $count, $i); } return $r; } // State-based way of generating combinations: function getCombination($values, $count, $index) { $result = []; for ($i = 0; $i < $count; $i++) { // Figure out where in the array to start from, given the external state and the internal loop state $pos = $index % count($values); // Append and continue $result[] = $values[$pos]; $index = ($index - $pos) / count($values); } return $result; } //maximize energy for given price function getBestProductCombinations($products,$price_limit){ //find all combinations where each product is either selected or not - true or false $combos = genCombinations([true,false],count($products)); $results = []; foreach($combos as $combo){ //loop through each combination and get a result $sum_price = 0;$items = [];$sum_energy = 0; foreach($combo as $i => $o){ //loop through the array of true/false values determining if an item is on or off if($o){ //if on, add item to result $sum_price += $products[$i]['price']; $sum_energy += $products[$i]['energy']; $items[] = $products[$i]; } } if($sum_price <= $price_limit){ //if sum of result is within the price limit, add to the results array $results[] = [ 'items' => $items, 'price' => $sum_price, 'energy' => $sum_energy ]; } } $best = $results[0];$ra = [$best]; foreach($results as $k => $result){ if($k === 0){continue;}//skip first iteration as it was set above //check if the energy is higher than the best, or if equal, check if the price is better if($result['energy'] > $best['energy'] || ($result['energy'] === $best['energy'] && $result['price'] < $best['price'])){ //reset best to the current result, reset return array $best = $result; $ra = [$best]; }else if($result['energy'] === $best['energy']){ //current result is the same as best, add it to the return array $ra[] = $result; } } return $ra; } echo '<pre>'.json_encode(getBestProductCombinations($products,10),JSON_PRETTY_PRINT).'</pre>'; 

Which then would give you:

[ { "items": [ { "id": 3, "price": 2.66, "energy": 300 }, { "id": 6, "price": 7, "energy": 1200 } ], "price": 9.66, "energy": 1500 } ] 

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