在数据库中,我有一个不同包装的价目表,每个包装至少包含以下产品之一:照片,平面图,EPC。示例 (ID |标题 |价格):
12 Photo 10.00
13 EPC 20.00
14 Floor Plan 20.00
15 4 Photos 40.00
16 4 Photos + EPC 55.00
17 4 Photos + Floor Plan 55.00
18 4 Photos + Floor Plan + EPC 75.00
etc...
现在我无法弄清楚如何始终确定最便宜的套餐组合。例如,如果我想要 5 张照片和一个平面图,则项目 17 + 12 的组合会比组合 5x12 和 14 (70.00) 便宜 (65.00)。我已将价目表转换为以下数组并将其传递给我的算法尝试,但它失败了......谁能把我推向正确的方向?
Array
(
[12] => Array
(
[price] => 10.00
[items] => Array
(
[0] => 1 // photo
[1] => 0 // floor plan
[2] => 0 // epc
)
)
[13] => Array
(
[price] => 20.00
[items] => Array
(
[0] => 0 // photo
[1] => 0 // floor plan
[2] => 1 // epc
)
)
[14] => Array
(
[price] => 20.00
[items] => Array
(
[0] => 0 // photo
[1] => 1 // floor plan
[2] => 0 // epc
)
)
[15] => Array
(
[price] => 40.00
[items] => Array
(
[0] => 4 // photo
[1] => 0 // floor plan
[2] => 0 // epc
)
)
[16] => Array
(
[price] => 60.00
[items] => Array
(
[0] => 4 // photo
[1] => 0 // floor plan
[2] => 1 // epc
)
)
etc...
)
发现者:
class CombinationFinder {
private $products = array();
public function __construct($products) {
$this->products = $products;
// sort by overall amount of items
uasort($this->products, function ($a, $b) {
$sum_a = array_sum($a['items']);
$sum_b = array_sum($b['items']);
if ($sum_a == $sum_b) {
return 0;
}
return $sum_a < $sum_b ? -1 : 1;
});
}
private function intersect($combo, $purchased) {
return array_map(function ($a, $b) {
$result = $b-$a;
return $result < 0 ? 0 : $result;
}, $combo, $purchased);
}
private function possibility($purchased, $limit) {
$price = 0;
$combination = array();
foreach($this->products as $pid => $combo) {
// if adding this combo exceeds limit, try next combo
if($price + $combo['price'] >= $limit) {
continue;
}
// see if combo helps
$test = $this->intersect($combo['items'], $purchased);
if(array_sum($test) === array_sum($purchased)) {
continue;
}
// add combo and deduct combo items
$combination[] = $pid;
$price += $combo['price'];
$purchased = $test;
// if purchased items are covered, break
if(array_sum($purchased) === 0) {
return array('price' => $price, 'combination' => $combination);
}
}
return false;
}
public function getCheapest($photos, $floorplans, $epc) {
$purchased = array((int)$photos, (int)$floorplans, (int)$epc);
$limit = 9999;
while($test = $this->possibility($purchased, $limit)) {
$limit = $test['price'];
$possibility = $test;
}
sort($possibility['combination'], SORT_NUMERIC);
echo 'Cheapest Combination: '.implode(', ', $possibility['combination']);exit;
}
}
我使用与上面建议的方法略有不同的方法解决了我的问题,使用了我认为是 Dijkstra 算法的变体。它采用与问题中显示的相同数组作为输入。
谢谢你们引导我穿过这个迷宫!!
class CombinationFinder {
private $products = array();
private $paths = array();
public function __construct($products) {
$this->products = $products;
// sort by price
uasort($this->products, function ($a, $b) {
if($a['price'] === $b['price']) {
return 0;
}
return $a['price'] > $b['price'] ? 1 : -1;
});
}
private function intersect($combo, $purchased) {
return array_map(function ($a, $b) {
$result = $b-$a;
return $result < 0 ? 0 : $result;
}, $combo, $purchased);
}
private function findPossibilities($purchased) {
$possibilities = array();
foreach($this->products as $pid => $combo) {
// possible path?
$remainder = $this->intersect($combo['items'], $purchased);
if(array_sum($remainder) === array_sum($purchased)) {
continue;
}
$possibility = new StdClass;
$possibility->step = $pid;
$possibility->cost = $combo['price'];
$possibility->remainder = $remainder;
$possibilities[] = $possibility;
}
return $possibilities;
}
private function determineCheapestPath() {
$minval = null;
$minkey = null;
foreach($this->paths as $key => $path) {
if(!is_null($minval) && $path->cost >= $minval) {
continue;
}
$minval = $path->cost;
$minkey = $key;
}
return $minkey;
}
private function walk() {
// determine currently cheapest path
$path = $this->determineCheapestPath();
// find possibilties for next move
if(array_sum($this->paths[$path]->remainder) === 0) {
return $path;
}
$possibilties = $this->findPossibilities($this->paths[$path]->remainder);
$move = array_shift($possibilties);
// update currently cheapest path
$this->paths[$path]->cost += $move->cost;
$this->paths[$path]->steps[] = $move->step;
$this->paths[$path]->remainder = $move->remainder;
return $this->walk();
}
// CONCEPT: from an initial set of possible paths, keep exploring the currently cheapest
// path until the destination is reached.
public function getCheapest($photos, $floorplans, $epc, $sqfeet) {
$purchased = array((int)$photos, (int)$floorplans, (int)$epc);
if(array_sum($purchased) === 0) {
return array();
}
// initial graph
foreach($this->findPossibilities($purchased) as $possibility) {
$path = new StdClass;
$path->cost = $possibility->cost;
$path->steps = array();
$path->steps[] = $possibility->step;
$path->remainder = $possibility->remainder;
$this->paths[] = $path;
}
$cheapest = $this->paths[$this->walk()];
return array_count_values($cheapest->steps);
}
}
NP完全问题。例如,您可以通过包含各种N
的N photos for N dollars
等条目,然后询问您是否必须支付超出必要的费用,将子集和问题编码到其中。
因为它是NP-Complete,所以没有已知的解决方案可以很好地扩展。但是,如果您的问题很小,则可以强行解决问题。
基本上,你想要这样的东西:
bestCombination = minBy(
filter(
allCombinations(list),
meetsCriteriaFunction
),
totalPriceOfListFunction
)
当然,你必须实现这些函数或使用它们在PHP中的任何等效功能。(对不起,我不太了解语法。