hal*_*.am 15 php algorithm optimization
假设我有三种产品:
产品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个Ç和一次一个.我该怎么办呢？
编辑产品数量可变.而且,具体的成本和功率是可变的.因此,可能有10种产品具有更清晰,更昂贵的价格标签.
编辑2正如我上面所说,我想计算可能的组合(复数).有些人似乎错过了我的描述.
这本来是一个背包问题,但因为你不只是寻找最佳解决方案,你也想找到所有可能的组合
获得最佳组合
例如,对于N = 4,S = {1,2,3},有四个解:{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,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);
}
}
}
更新的答案
我坚持原来的答案,但后来得出了一个明确的解决方案.不幸的是,我不熟悉PHP,因此我将介绍的实现(写得不好)F#.
让您的问题变得有趣的一点是,您不是在寻找最佳解决方案,而是寻求所有可行的解决方案.正如我在原始答案中指出的那样,这很棘手,因为可行解决方案的集合是无限的.举例来说,如果你想生产65个单位,你可以使用13xA,产生5x13 = 65的功率.但是,显然,任何包含超过13个单位的A的解决方案也将是一个解决方案.
您无法从函数返回无限集.你需要的是所有"边界"案例的集合:
例如,解S = {A = 13; B = 0; C = 0}是边界情况.从任何产品中移除一个单元,这是不可行的 - 如果组合是这样的,对于每个产品,它包含比S更多的单元,它是一个有效的解决方案,但由S"支配".
换句话说,我们无法返回所有可能的解决方案,但我们可以返回分离可行和不可行解决方案的"限制".
还要注意,产品的成本在这里是无关紧要的 - 一旦你有一组边界情况,计算解决方案的成本是微不足道的.
鉴于您指定产品的数量可以是任意的,这听起来像一个明确的递归案例.
如果你没有产品,解决方案很简单 - 没有解决方案.如果您有1个产品,解决方案是天花板(目标/产品.电源)如果你有2个产品,比如A:5和B:2,目标是10,你可以
A最大化,所以我们完成了.
请注意,我通过降低功率对A和B进行了排序.未排序的列表也可以工作,但是你会产生"无用的"边界点.例如,我们会得到[1 B; 2 A]和[2 B; 2 A].
这个想法可以扩展到一个完整的递归,沿着线
Given a list of Products and a remaining Target power to achieve,
If the Product is the last one in the list, use ceiling of Target/product Power,
Else take every possible combination of the head product from 0 to max, and
Search deeper, decreasing Target Power by the units supplied by the Product selected.
下面是一个简单的F#实现,可以轻松改进,并有望传达这个想法.单位函数返回具有提供目标Power所需的Power值的产品的最小单位数,并且递归函数solve将组合构建为解决方案列表,具有Product Id的元组和要使用的单位数:
type Product = { Id: string; Power: int }
let A = { Id = "A"; Power = 5 }
let B = { Id = "B"; Power = 9 }
let C = { Id = "C"; Power = 15 }
let products = [ A; B; C ] |> List.sortBy(fun e -> - e.Power)
let units (target: int) (value: int) =
if target < 0
then 0
else
(float)target / (float)value |> ceil |> (int)
let rec solve (products: Product list)
(current: (string * int) list)
(solutions: (string * int) list list)
(target: int) =
match products with
| [ ] -> [ ]
| [ one ] -> ((one.Id, (units target one.Power)) :: current) :: solutions
| hd :: tl ->
let max = units target hd.Power
[ 0 .. max ]
|> List.fold (fun s u ->
solve tl ((hd.Id, u) :: current) s (target - u * hd.Power)) solutions
我会这样运行:
> solve [B;A] [] [] 65;;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : (string * int) list list =
[[("A", 0); ("B", 8)]; [("A", 1); ("B", 7)]; [("A", 3); ("B", 6)];
[("A", 4); ("B", 5)]; [("A", 6); ("B", 4)]; [("A", 8); ("B", 3)];
[("A", 10); ("B", 2)]; [("A", 12); ("B", 1)]; [("A", 13); ("B", 0)]]
请注意,解决方案的数量会相当快.我运行了你的例子,它产生了28个解决方案.随着产品数量和目标功率的增加,边界解决方案的数量将会大幅增加.
我根本不能在PHP中编码,但我认为它支持递归 - 也许有人会在PHP中显示递归解决方案？无论如何,我希望这会有所帮助.
一个有趣的问题是,如果产品可以以非整数量购买,问题会有多么不同.在这种情况下,边界实际上是一个表面(我相信多面体); 如何充分描述它将是一个有趣的问题!
原始答案
除非我误解了你的问题,否则你所描述的是优化中已知的整数线性规划问题,并有完善的算法来解决它们.你的问题听起来像是饮食问题的变化(给定成分,找到最便宜的方法来获得足够的卡路里来生存),线性规划的原型之一,具有整数变量约束.
首先,所述问题的解决方案有无数的解决方案; 假设5 x A是您问题的解决方案,那么任何超过5个A单位的组合也将满足您的要求.
编辑:我意识到我可能误解了你的问题 - 我以为你可以购买任何数量的每种产品.如果你只能购买1个单元,这是一个更容易的问题:它仍然是一个整数编程问题,但更简单的问题是背包问题.
另请注意,如果您可以使用非整数数量的产品(对您来说似乎不是这样),那么您的问题就更容易解决了.
重述问题最明显的方法,使其成为可以轻松解决的标准优化问题:
找到具有最小总成本的n个产品的组合,但受限于所传递的总能量高于期望阈值.(我假设总成本和总能量都是A,B,C ......购买数量的线性函数).
我认为这实际上是你真正想要的 - 对你的问题最好的解决方案.如果你真的对列举所有解决方案感兴趣,那么解决它的一种方法是确定定义可行集的边界(即几何边界,如果你在一边,你知道它不是解决方案,否则它是).如果您使用不必是整数的数字,这会容易得多.
希望这可以帮助!
| 归档时间： |
|
| 查看次数： |
850 次 |
| 最近记录： |