计算哪些产品一起将提供所要求的功率 [英] Calculate which products together would deliver the requested power
问题描述
比方说，我有三只产品：
Let's say I've got three products:
产品A 将提供5权力。成本50元。
Product A Will deliver 5 power. Costs 50.
产品B 将提供9电源。成本80。
Product B Will deliver 9 power. Costs 80.
产品C 将提供15供电。成本140。
Product C Will deliver 15 power. Costs 140.
我想知道什么样的产品组合，我可以买的时候，我需要7权力。我可以买两个的 A 但之一的 B 更便宜。
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.
当我需要65的功率。我将需要4倍的 C 和1次的 A （费用680）。但我也可以去七的 B 产品和一个 A （费用610）。
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;
}
}
}
此示例code只会给我4次的 C 并一次性的 A 。我应该怎么做呢？
This sample code will only give me 4 times C and one time A. How should I go about it?
修改产品数量是可变的。另外，特定成本和功率是可变的。因此，有可能是10产品的幼儿，更昂贵的价格标签。
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.
编辑2 正如我前面所说，我想计算出可能的组合（复数）。有些人似乎已经错过了，在我的描述。
EDIT 2 As I said above, I want to calculate the possible combinations (plural). Some people seem to have missed that in my description.
推荐答案
这将是一个背包问题，而是因为你是不是不只是寻找最佳解决方案你也想找出所有可能的组合
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
例如，对于N = 4，S = {1,2,3}，有四种解决方案：{1,1,1,1}，{1,1,2} {2,2}，{1,3}。
For example, for N = 4,S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}.
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个或更多的产品组合，但门槛非常快
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;
输出
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);
}
}
}
这篇关于计算哪些产品一起将提供所要求的功率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
