Как разбить эти продукты на пакеты?

Question

У меня есть эта группа продуктов:

Product  Quantity Weight Per Unit 
pro#1   7    5kg 
pro#2   5    5kg 

Я хочу, чтобы разделить эти продукты в пакеты, но максимальный вес пакета составляет 22кг.

Предположим, что у меня есть эта таблица в массиве, мне нужен алгоритм для решения этой проблемы.

Это то, что я пробовал до сих пор.

$products = array(
    array('weight'=> 5, 'quantity' => 7), 
    array('weight'=> 5, 'quantity' => 5), 
); 
$max_weight = 22; 
$packs = array(); 
$packs_count = 1; 
foreach ($products as $product){ 
    while ($product['quantity'] != 0) { 
     $pack[$packs_count]['weight'] = $pack[$packs_count]['weight'] +$product['weight']; 
     if($pack[$packs_count]['weight'] >$max_weight){ 
      $pack[$packs_count]['weight'] = $pack[$packs_count]['weight'] - $product['weight']; 
      $packs_count++; 
     } 
     $product['quantity']--; 
} 
} 

Код не может получить последний пакет в порядке.

Answer 1

Я решил проблему, используя этот код в PHP, любые дополнительные мысли были бы замечательными. Спасибо, в любом случае.

$products = array(
    array('weight'=> 4, 'quantity' => 5), 
    array('weight'=> 8, 'quantity' => 3), 
); 
$max_weight = 22; 
$packs = array(); 
$packs_count = 1; 

foreach ($products as $product){ 
    while ($product['quantity'] != 0) { 
     $pack[$packs_count]['weight'] = $pack[$packs_count]['weight'] +$product['weight']; 
     if($pack[$packs_count]['weight'] > $max_weight){ 
      $pack[$packs_count]['weight'] = $pack[$packs_count]['weight'] - $product['weight']; 
      $packs_count++; 
      $pack[$packs_count]['weight'] = $product['weight']; 

     } 
     $product['quantity']--; 
    } 
} 

print_r($pack); 

Answer 2

То, что вы пытаетесь достичь, не совсем ясен для меня. Я сделаю предположение, что вы пытаетесь свести к минимуму общее количество пакетов, созданных алгоритмом. Если это действительно так, то то, что вы пытаетесь решить, - это Bin Packing Problem. Этот алгоритм NP-жесткий, однако существуют простые эвристики, которые ведут себя (возможно) лучше, чем тот, который вы предлагаете. Например, первый алгоритм уменьшения сглаживания, который будет состоять из сортировки элементов от самого большого до самого маленького и вставки их в первый ящик, в котором они подходят (создание нового бункера, если ни один из существующих не имеет достаточной оставшейся емкости)