介绍
这本来是一个背包问题，但是因为您不仅要寻找最佳解决方案，还希望找到所有可能的组合
然后你可以解决这个子集和问题+硬币变化得到：
- 列出所有可能的组合，而不仅仅是总组合
获得最佳组合
例如，对于 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);
}
}
}