算法：最便宜的產品包組合

Question

在數據庫中，我有一個不同包的價目表，每個包至少包含以下產品之一：照片，平面圖，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; 
    } 
} 

Answer 1

我已經解決了我的問題，使用的方法與上面提出的略有不同，使用我認爲是Dijkstra's algorithm的變體。它採用與問題中所示相同的數組作爲輸入。

謝謝大家指導我通過這個迷宮！

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); 
    } 
} 

Answer 2

這是一個NP完全問題。例如，您可以將subset-sum問題編碼到其中，方法是將N photos for N dollars這樣的條目包含在各種N中，然後詢問您是否必須支付超過必要的費用。

因爲它是NP-Complete，所以沒有已知的解決方案可以很好地擴展。但是如果你的問題很小，你可以蠻橫的強制解決方案。

基本上，你想要的東西，如：

bestCombination = minBy(
    filter(
     allCombinations(list), 
     meetsCriteriaFunction 
    ), 
    totalPriceOfListFunction 
) 

當然，你必須執行這些無論其等效在PHP函數或使用。 （對不起，我不太清楚語法）