Calculate which products together would deliver the requested power

Question

Let's say I've got three products:

Product A Will deliver 5 power. Costs 50.

Product B Will deliver 9 power. Costs 80.

Product C Will deliver 15 power. Costs 140.

I want to know what combination of products I could buy when I need 7 power. I could buy two of A but one of B is cheaper.

When I'd need 65 power. I would need 4 times C and 1 time A (costs 680). But I could also go for seven B products and one A (costs 610).

I am looking for a way to calculate the possible combinations of products for the given amount of power I need.

The way I tried doing this doesn't give me what I want:

// $products are sorted DESC on their $power
$power = 65
 while( $power > 0 ) {
    foreach( $products as $productPower ) {
        if( ( $productPower > $power && $power - $productPower > 0 ) || $productPower == end( $products ) ) {
            // Add product to list
            $power -= $productPower;
            break;
        }
    }
 }

This sample code will only give me 4 times C and one time A. How should I go about it?

EDIT The number of products is variable. Also, the specific cost and power is variable. So there may be 10 products with cheeper and more expensive price tags.

EDIT 2 As I said above, I want to calculate the possible combinations (plural). Some people seem to have missed that in my description.

Answer 1

Introduction

This would have been a Knapsack problem but because you are not not just looking for the optimal solution you also want to find all possible combination

Then you can solve this Subset sum problem + Coin Change to get :

• List all possible Combination and not just total combination

• Get Best Combination

  For example, for N = 4,S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.

Example 1

echo "<pre>";
$start = microtime(true);

// Start Finder
$finder = new CombinationFinder(65);

// Add Produts
$finder->addProduct(new Product("A", 5, 50));
$finder->addProduct(new Product("B", 9, 80));
$finder->addProduct(new Product("C", 15, 140));

// Output All Found Combinations
foreach ( $finder as $key => $sales ) {
    echo $sales->getName(), "\t\t\t", $sales->getCombinationCost(), PHP_EOL;
}

// Get Best Combination
echo "Combination: ", $finder->getBestCombination()->getName(), PHP_EOL;
echo "Cost: ", number_format($finder->getBestCombination()->getCombinationCost(), 2), PHP_EOL;

// Total Time
echo PHP_EOL, microtime(true) - $start;

Output

Top Combinations

["A",1],["C",4]                 610
["A",1],["B",5],["C",1]         590
["A",4],["C",3]                 620
["A",4],["B",5]                 600
["A",7],["C",2]                 630
["A",10],["C",1]                640
["A",13]                        650

Best Combination

Combination: ["A",1],["B",5],["C",1]
Cost: 590.00

Total Time

0.2533269405365

Best Combination

You can see the best Combination is A*1 ,B*5 ,C*1 .. Break down

            A          B           C
Power : 5   *  1 +  9  *  5 +  15  *  1    =   65
Cost  : 50  *  1 +  80 *  5 +  140 *  1    =   590   <---- Better than 610.00   

Example 2

The class can be use for 2, 3 , 4 or more product combination and yet sill very fast

echo "<pre>";
$start = microtime(true);

// Start Finder
$finder = new CombinationFinder(65);

// Add Produts
$finder->addProduct(new Product("A", 5, 50));
$finder->addProduct(new Product("B", 9, 80));
$finder->addProduct(new Product("C", 15, 140));
$finder->addProduct(new Product("D", 20, 120)); // more product class

$finder->run(); // just run

// Get Best Combination
echo "Combination: ", $finder->getBestCombination()->getName(), PHP_EOL;
echo "Cost: ", number_format($finder->getBestCombination()->getCombinationCost(), 2), PHP_EOL;

// Total Time
echo PHP_EOL, microtime(true) - $start;

Output

Combination: ["A",1],["D",3]    //<---------------------- Best Combination
Cost: 410.00

Time Taken

1.1627659797668  // less than 2 sec 

Class Used

class Product {
    public $name;
    public $power;
    public $cost;
    public $unit;

    function __construct($name, $power, $cost) {
        $this->name = $name;
        $this->power = $power;
        $this->cost = $cost;
        $this->unit = floor($cost / $power);
    }
}



class Sales {
    /**
     *
     * @var Product
     */
    public $product;
    public $count;
    public $salePower;
    public $saleCost;

    function __construct(Product $product, $count) {
        $this->product = $product;
        $this->count = $count;
        $this->salePower = $product->power * $count;
        $this->saleCost = $product->cost * $count;
    }
}



class SalesCombination {
    private $combinationPower;
    private $combinationCost;
    private $combinationName;
    private $combinationItems;
    private $args;

    function __construct(array $args) {
        list($this->combinationPower, $this->combinationCost, $this->combinationItems) = array_reduce($args, function ($a, $b) {
            $a[0] += $b->salePower;
            $a[1] += $b->saleCost;
            $a[2] = array_merge($a[2], array_fill(0, $b->count, $b->product->name));
            return $a;
        }, array(0,0,array()));
        $this->args = $args;
    }

    function getName() {
        $values = array_count_values($this->combinationItems);
        $final = array();
        foreach ( $values as $name => $amount ) {
            $final[] = array($name,$amount);
        }
        return substr(json_encode($final), 1, -1);
    }

    function getCombinationPower() {
        return $this->combinationPower;
    }

    function getCombinationCost() {
        return $this->combinationCost;
    }
}




class CombinationFinder implements IteratorAggregate, Countable {
    private $sales;
    private $products = array();
    private $power;
    private $found = array();
    private $bestCombination = null;
    private $run = false;

    function __construct($power) {
        $this->power = $power;
    }

    function addProduct(Product $product) {
        $this->products[] = $product;
    }

    function getBestCombination() {
        return $this->bestCombination;
    }

    function getFound() {
        return $this->found ?  : array();
    }

    public function getIterator() {
        if ($this->run === false) {
            $this->run();
        }
        return new ArrayIterator($this->found);
    }

    public function count() {
        return count($this->found);
    }

    function run() {
        $this->run = true;
        $this->buildSales();
        $u = new UniqueCombination($this->sales);
        $u->setCallback(array($this,"find"));
        $u->expand();
    }

    function find() {
        $salesCombination = new SalesCombination(func_get_args());
        if ($salesCombination->getCombinationPower() == $this->power) {
            isset($this->bestCombination) or $this->bestCombination = $salesCombination;
            $salesCombination->getCombinationCost() < $this->bestCombination->getCombinationCost() and $this->bestCombination = $salesCombination;
            $this->found[sha1($salesCombination->getName())] = $salesCombination;
        }
    }

    function buildSales() {
        $total = count($this->products);
        foreach ( $this->products as $product ) {
            $max = floor($this->power / $product->power);
            for($i = 1; $i <= $max; $i ++) {
                $this->sales[$product->name][] = new Sales($product, $i);
            }
        }
    }
}

class UniqueCombination {
    private $items;
    private $result = array();
    private $callback = null;

    function __construct($items) {
        $this->items = array_values($items);
    }

    function getResult() {
        return $this->result;
    }

    function setCallback($callback) {
        $this->callback = $callback;
    }

    function expand($set = array(), $index = 0) {
        if ($index == count($this->items)) {
            if (! empty($set)) {
                $this->result[] = $set;
                if (is_callable($this->callback)) {
                    call_user_func_array($this->callback, $set);
                }
            }
            return;
        }
        $this->expand($set, $index + 1);
        foreach ( $this->items[$index] as $item ) {
            $this->expand(array_merge($set, array($item)), $index + 1);
        }
    }
}

Answer 2

Updated answer

I stand with my original answer, but have since derived an explicit solution. Unfortunately, I am not versed in PHP, so the implementation I'll present is in (poorly written) F#.

The point which makes your question interesting is that you are not looking for THE best solution, but for all feasible solutions. As I pointed out in my original answer, this is tricky, because the set of feasible solutions is infinite. As an illustration, if you want to produce 65 units, you can use 13xA, which yields a power of 5x13 = 65. But then, obviously, any solution which contains more than 13 units of A will also be a solution.

You can't return an infinite set from a function. What you need here is the set of all "boundary" cases:

• if a solution contains as many units as a boundary case for all products, it is valid
• if a unit can be removed from a boundary case and it is still feasible, it is not feasible anymore.

For instance, the solution S = { A = 13; B = 0; C = 0 } is a boundary case. Remove one unit from any product, and it is not feasible - and if a combination is such that for every product, it contains more units than S, it is a valid solution, but "dominated" by S.

In other words, we cannot return all possible solutions, but we can return the "limit" that separates feasible and unfeasible solutions.

Note also that the cost of the Products is irrelevant here - once you have the set of boundary cases, computing the cost of a solution is trivial.

Given that you specify that the number of products could be arbitrary, this sounds like a clear case for recursion.

If you have no product, the solution is trivially empty - there is no solution. If you have 1 product, the solution is ceiling (target / product.Power) If you have 2 products, say A:5 and B:2, with a target of 10, you could

• use 0 of A -> remaining target is 10, use 5 B (or more)
• use 1 of A -> remaining target is 10 - 5, use 3 B (or more)
• use 2 of A -> remaining target is 10 - 10, use 0 B (or more)

A is maxed out, so we are done.

Note that I sorted A and B by decreasing Power. An unsorted list would work, too, but you would produced "useless" boundary points. For instance, we would get [1 B; 2 A], and [2 B; 2 A].

The idea can be extended to a full recursion, along the lines of

Given a list of Products and a remaining Target power to achieve,
If the Product is the last one in the list, use ceiling of Target/product Power,
Else take every possible combination of the head product from 0 to max, and
Search deeper, decreasing Target Power by the units supplied by the Product selected.

Below is a simple F# implementation, which could easily be improved upon, and will hopefully convey the idea. The units function returns the minimum number of units of a product with Power value required to supply target Power, and the recursive function solve builds up the combinations into a List of solutions, tuples with a Product Id and the number of units to use:

type Product = { Id: string; Power: int }
let A = { Id = "A"; Power = 5 }
let B = { Id = "B"; Power = 9 }
let C = { Id = "C"; Power = 15 }

let products = [ A; B; C ] |> List.sortBy(fun e -> - e.Power)

let units (target: int) (value: int) =
    if target < 0
    then 0
    else
        (float)target / (float)value |> ceil |> (int)

let rec solve (products: Product list) 
              (current: (string * int) list) 
              (solutions: (string * int) list list) 
              (target: int) =
    match products with
    | [ ] -> [ ]
    | [ one ] -> ((one.Id, (units target one.Power)) :: current) :: solutions
    | hd :: tl ->
        let max = units target hd.Power
        [ 0 .. max ]
        |> List.fold (fun s u ->
            solve tl ((hd.Id, u) :: current) s (target - u * hd.Power)) solutions

I would run it this way:

> solve [B;A] [] [] 65;;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : (string * int) list list =
  [[("A", 0); ("B", 8)]; [("A", 1); ("B", 7)]; [("A", 3); ("B", 6)];
   [("A", 4); ("B", 5)]; [("A", 6); ("B", 4)]; [("A", 8); ("B", 3)];
   [("A", 10); ("B", 2)]; [("A", 12); ("B", 1)]; [("A", 13); ("B", 0)]]

Note that the number of solutions will increase pretty fast. I ran your example, which yielded 28 solutions. As the number of products and the target power increases, the number of boundary solutions will expand quite a bit.

I can't code in PHP at all, but I assume it supports recursion - maybe someone will show a recursive solution in PHP? In any case, I hope this helps.

An interesting side question would be how different the problem would be, if the products could be purchased in non-integer quantities. In that case, the boundary would really be a surface (a polyhedron I believe); how to describe it adequately would be an interesting problem!

Original answer

Unless I am misunderstanding your question, what you describe is what is known in optimization as an Integer Linear Programming problem, with well established algorithms to resolve them. Your problem sounds like a variation of the Diet problem (given ingredients, find the cheapest way to get enough calories to survive), one of the archetypes of Linear Programming, with integer variable constraints.

First, the solution to your problem as stated has an infinite numbers of solutions; suppose that 5 x A is a solution to your problem, then any combination with more than 5 units of A will also satisfy your requirements.

Edit: I realize I might have misunderstood your problem - I assumed you could buy any quantity of each product. If you can buy only 1 unit of each, this is an easier problem: it is still an integer programming problem, but a simpler one, the Knapsack problem.

Note also that if you can by non-integer quantities of the products (doesn't seem to be the case for you), your problem is significantly easier to solve.

The most obvious way to restate your problem, which make it a standard optimization problem that can be solved fairly easily:

Find the combination of n Products which has the minimum total cost, subject to constraint that the total energy delivered is above desired threshold. (I assume that both the total cost and total energy delivered are linear functions of the quantity of A, B, C... purchased).

I assume this is actually what you really want - the best possible solution to your problem. If you are really interested in enumerating all the solution, one way to go about it is to identify the boundaries which define the feasible set (i.e. the geometric boundary such that if you are on one side you know it's not a solution, otherwise it is). This is much easier if you are working with numbers that don't have to be integers.

Hope this helps!