Блог

Проблема заключается в следующем:

Компания поставляет виджеты в наборе размеров упаковки:

• 250
• 500
• 1000
• 2000
• 5000

Клиенты могут заказать любое количество виджетов, но применяются следующие правила:

• Можно отправлять только целые пакеты и …
• Не следует отправлять больше виджетов, чем необходимо, и …
• Должно быть отправлено как можно меньше упаковок

Несколько примеров, показывающих количество заказанных виджетов и требуемое количество упаковок и размеры для правильного выполнения заказа:

• 1 (1 x 250)
• 251 (1 x 500)
• 501 (1 x 500 и 1 x 250)
• 12001 (2 x 5000 и 1 x 2000 и 1 x 250)

Я рассмотрел некоторые алгоритмы (жадный обмен монетами, LAFF и т.д.), Поскольку они, похоже, обеспечивают аналогичные решения. Однако в идеале я ищу масштабируемый объектно-ориентированный подход к решению этой проблемы.

Вот что я придумал до сих пор:

 <?php

function countWidgets($amount) 
{ 
    $packs = array(5000, 2000, 1000, 500, 
                  250); 
    $packCounter = array(0, 0, 0, 0, 0); 
    $packsCount = count($packs);

    // loop packs
    for ($i = 0; $i < $packsCount; $i  )  
    { 
        if ($amount >= $packs[$i]) 
        { 
            $packCounter[$i] = intval($amount /  
                                      $packs[$i]); 
            $amount = $amount -  
                      $packCounter[$i] *  
                      $packs[$i]; 
        } 
    }

    // if remainder
    if ($amount > 0) {
        // and if smallest pack size populated
        if ($packCounter[4] == 1) {
            // clear smallest pack size
            $packCounter[4] = 0;
            // increment next biggest pack size
            $packCounter[3]  = 1;
        } else {
            // increment smallest pack size
            $packCounter[4]  =1;
        }
    }


    // Print packs 
    echo ("Pack ->"."n"); 
    for ($i = 0; $i < $packsCount; $i  )  
    { 
        if ($packCounter[$i] != 0)  
        { 
            echo ($packs[$i] . " : " . 
                  $packCounter[$i] . "n"); 
        } 
    } 
} 

$amount = 251; 
countWidgets($amount);
  

Хорошо, я согласен, что это немного сложнее, чем я предполагал вчера. У вас в основном есть два противоположных требования:

1. Не следует отправлять больше виджетов, чем необходимо.
2. Следует отправлять как можно меньше упаковок.

Вы не можете выполнить оба. Итак, если я попытался отправить 1200 виджетов, в правиле 2 говорится, что я должен отправить пакет из 2000, однако в правиле 1 говорится, что я должен отправить 2 пакета: один из 1000 и один из 250. Какое правило должно преобладать?

Я решил, что правило 1 должно преобладать в решении ниже. Причина в том, что ни один клиент не хочет больше виджетов, чем это абсолютно необходимо.

 $packSizes = [ 250,
               500,
              1000,
              2000,
              5000];

function optimizePacks($packSizes,$number)
{
    rsort($packSizes);
    $requiredPacks = array_fill_keys($packSizes,0);
    foreach ($packSizes as $size) {
        $packs = floor($number/$size);
        if ($packs > 0) {
            $requiredPacks[$size] = $packs;
            $number -= $packs*$size;
        }
    }
    if ($number > 0) $requiredPacks[min($packSizes)]  ;
    return $requiredPacks;
}

$packs = optimizePacks($packSizes,6666);

print_r($packs);
  

Это будет работать для любого массива пакетов разного размера и любого количества виджетов. Результатом этого кода является:

Массив ( [5000] => 1 [2000] => 0 [1000] => 1 [500] => 1 [250] => 1 )

Что на один пакет больше, чем требовало бы правило 2 (один из 5000 и два из 1000). Конечно, можно было бы допустить преобладание правила 2, но я не могу выполнить оба правила.