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

栏目: PHP · 发布时间: 6年前

内容简介:代码日志版权声明:翻译自:http://stackoverflow.com/questions/13211189/calculate-which-products-together-would-deliver-the-requested-power

假设我有三个产品:

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

代码日志版权声明:

翻译自:http://stackoverflow.com/questions/13211189/calculate-which-products-together-would-deliver-the-requested-power


以上所述就是小编给大家介绍的《php – 计算哪些产品在一起将提供所要求的电力》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

强化学习精要

强化学习精要

冯超 / 电子工业出版社 / 2018-6 / 80

《强化学习精要:核心算法与TensorFlow 实现》用通俗幽默的语言深入浅出地介绍了强化学习的基本算法与代码实现,为读者构建了一个完整的强化学习知识体系,同时介绍了这些算法的具体实现方式。从基本的马尔可夫决策过程,到各种复杂的强化学习算法,读者都可以从本书中学习到。本书除了介绍这些算法的原理,还深入分析了算法之间的内在联系,可以帮助读者举一反三,掌握算法精髓。书中介绍的代码可以帮助读者快速将算法......一起来看看 《强化学习精要》 这本书的介绍吧!

html转js在线工具
html转js在线工具

html转js在线工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具