In a database, I have a price list of different packages each consisting of at least one of the following products: Photo, Floor Plan, EPC. Example (ID | Title | Price):
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...
Now I can't get my head around how I can always determine the cheapest package combination. For example if I wanted 5 photos and a floor plan, the combination of items 17 + 12 would be cheaper (65.00) than combination 5x12 and 14 (70.00). I've translated the price list into the following array and passed it to a my algorithm attempt, but it fails... Can anyone nudge me in the right direction?
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...
)
The Finder:
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;
}
}
