StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<h2> Introduction </h2> <p>This would have been a <a href="http://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow noreferrer">Knapsack problem</a> but because you are not not just looking for the optimal solution you also want to find all possible combination</p> <p>Then you can solve this <a href="http://en.wikipedia.org/wiki/Subset_sum_problem" rel="nofollow noreferrer">Subset sum problem</a> + <a href="http://www.algorithmist.com/index.php/Coin_Change" rel="nofollow noreferrer">Coin Change</a> to get :</p> <ul> <li>List all possible Combination and not just total combination</li> <li><p>Get Best Combination </p> <p><strong>For example</strong>, for N = 4,S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.</p></li> </ul> <h2>Example 1</h2> <pre><code>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; </code></pre> <h2>Output</h2> <p><strong>Top Combinations</strong></p> <pre><code>["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 </code></pre> <p><strong>Best Combination</strong></p> <pre><code>Combination: ["A",1],["B",5],["C",1] Cost: 590.00 </code></pre> <p><strong>Total Time</strong></p> <pre><code>0.2533269405365 </code></pre> <h2>Best Combination</h2> <p>You can see the best Combination is <code>A*1 ,B*5 ,C*1</code> .. Break down </p> <pre><code> A B C Power : 5 * 1 + 9 * 5 + 15 * 1 = 65 Cost : 50 * 1 + 80 * 5 + 140 * 1 = 590 <---- Better than 610.00 </code></pre> <h2>Example 2</h2> <p>The class can be use for 2, 3 , 4 or more product combination and yet sill very fast </p> <pre><code>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; </code></pre> <p><strong>Output</strong> </p> <pre><code>Combination: ["A",1],["D",3] //<---------------------- Best Combination Cost: 410.00 </code></pre> <p><strong>Time Taken</strong> </p> <pre><code>1.1627659797668 // less than 2 sec </code></pre> <h2>Class Used</h2> <pre><code>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); } } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload