php – 计算哪些产品在一起将提供所要求的电力

假设我有三个产品：

产品A

将提供5个电源.成本50.

产品B将提供9个电源.成本80.

产品C将提供15个电源.成本140.

当我需要7个电源时,我想知道我可以购买什么产品的组合.我可以买到两个A,但是B中的一个是便宜的.

当我需要65个电源我需要4次C和1次A(费用680).但我也可以去七个B产品和一个A(费用610).

我正在寻找一种方法来计算我需要的给定功率的产品的可能组合.

我这样做的方式不会给我我想要的：

// $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;
        }
    }
 }

这个示例代码只会给我4次C和一次A.我该怎么办？

编辑产品数量是可变的.此外,具体成本和功率是可变的.所以可能会有10个产品与cheeper和更昂贵的价格标签.

编辑2如上所述,我想计算可能的组合(复数).有些人似乎在我的描述中错过了.

介绍

这将是一个 Knapsack problem ,但因为你不只是寻找最佳的解决方案,你也想找到所有可能的组合

那么你可以解决这个 Subset sum problem Coin Change 得到：

>列出所有可能的组合,而不仅仅是总组合

>获得最佳组合

例如,对于N = 4,S = {1,2,3},有四个解：{1,1,1,1},{1,1,2},{2,2},{1, 3}.

实施例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;

产量

顶级组合

["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

最佳组合

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

总时间

0.2533269405365

最佳组合

你可以看到最好的组合是A * 1,B * 5,C * 1 ..分解

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

实施例2

该类可以用于2,3,4或更多的产品组合,并且非常快

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;

产量

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

所用的时间

1.1627659797668  // less than 2 sec

使用类

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);
        }
    }
}