students - standard algorithm for addition




algorithm to find best combination (7)

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.


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


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
    }
]

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.



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






math