php - 基于外壳尺寸的最低成本

Question

我正在开发 wine 的运输模块，想知道是否有人可以帮助我 - 基本上:

Wine 可以 8 瓶、12 瓶或 15 瓶装运，每箱都有自己的价格。该模块需要获取订单中的瓶子总数，并计算出哪种箱子组合给出的价格最低。例如，在 31 瓶的订单中，最低价格计算为 1 箱 15 瓶和两箱 8 瓶(而不是 2 箱 15 瓶和 1 瓶 8 瓶，或 2 箱 12 瓶和 1 箱 8 瓶)。目前，我有以下内容，几乎可以工作，但错过了一些可能的组合

    foreach ($rates as $case_size => $case_price) 
    {
      $price = floor($total_bottles / $case_size) * $case_price;
      $rem = $total_bottles % $case_size;
      if($rem > 12)
      {
       //needs to use another case of 15 
       $price = $price + $rates[15];
      }
      elseif($rem > 8)
      {
        //needs an extra case of 12
        $price = $price + $rates[12];
      }
      elseif($rem > 0)
      {
        //needs an extra case of 8
        $price = $price + $rates[8];
      }
      $quotes[] = $price;
    }

    return min($quotes);

Answer 1

从您的帖子中可以看出，最具性价比的系统不仅是每瓶容器使用成本最低的系统，还需要在灌装容器时效率最高。但是，您的算法只考虑使用尽可能少的大盒子。您需要一种算法来完全填充每种可能的情况。

我会这样做:使用递归程序找到最能完全填充每种情况的组合。

function fit_case($number, $case_size) {
     $rem = $number % $case_size;
     $next_size=magic_voodo0();
     if($rem==0) {        //if perfectly fills it you're done
           return ($number/$case_size)*$rates[$case_size];
     } else if(($rem % $next_size)/$next_size>.5) {               
     //if over 50% fills the next case add the next smaller case
           return floor($number/$case_size)*$rates[$case_size]+fit_case($rem, $next_size);
      } else {        //otherwise back off 1 of the biggest cases, and fill the rest
         return (floor($number/$case_size)-1)*$rates[$case_size]+fit_case($rem, $next_size);

希望这对您有所帮助。