Как реализовать такой алгоритм?

Question

Скажите, что есть x количество ящиков, каждая коробка содержит «инвентарь» букв A-Z, каждый из которых содержит 1 или более букв.

Теперь предположим, что мне нужно следующее:

• 6 Как
• 2 Bs
• 1 C

Как получить список всех возможных комбинации/перестановкой коробки что может предоставить мне письма, которые мне нужны?

Алгоритм должен также создавать комбинацию ящиков для удовлетворения моих требований. Например: скажем, что Box-1 имеет только 4 As и Box-2 имеет 1 A ​​и Box-3 имеет 1 A, мне нужен результат алгоритма, чтобы указать, что 6 As может быть выполнено через 3 поля.

Какова основная логика решения такой проблемы. Есть ли какие-то конкретные алгоритмы, которые мне нужно изучать?

EDIT 1:

За предложение DCP, вот это моя попытка, что реализации PHP:

$boxes = array(
    // box 1 
    array(
     'A' => 6, 
     'B' => 4, 
     'C' => 10 
    ), 
    // box 2 
    array(
     'A' => 8, 
     'B' => 4, 
     'C' => 2 
    ), 
    // box 3 
    array(
     'A' => 1, 
     'B' => 1, 
     'C' => 0 
    ) 
); 

$n = count($boxes); 

for ($mask = 0; $mask <= (1 << $n) - 1; $mask++) 
{ 
    $tots = array(); 
    for ($i = 0; $i < $n; $i++) 
    { 
     if (((1 << $i) & $mask) != 0) 
     { 
      // this is a selected box for this mask, add the A's, B's etc. for this box to the total 
      $tots[0] += $boxes[$i]['A']; 
      $tots[1] += $boxes[$i]['B']; 
      $tots[2] += $boxes[$i]['C']; 
     } 
     // check the tots array to see if it meets the letter requirements. If it does, 
     // then this is a valid combination of boxes. 
    } 
} 

Answer 1

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

// assume n is number of boxes, and boxes is the array of boxes 
for(int mask = 0; mask <= (1<<n)-1; ++mask) { 
    int tots[26]; 
    for(int i = 0; i < n; ++i) { 
    if (((1<<i)&mask) != 0) { 
     // this is a selected box for this mask, add the A's, B's etc. for this box to the total 
     tots[0] += number of A's in box i 
     tots[1] += number of B's in box i 
     . 
     . 
    } 
    // check the tots array to see if it meets the letter requirements. If it does, 
    // then this is a valid combination of boxes. 
    } 
}