Скажем, есть x коробок, каждая коробка содержит «инвентарь» букв от A до Z, причем запас каждой буквы составляет 1 или более.
Теперь скажем, мне нужно следующее:
- 6 As
- 2 Bs
- 1 C
Как мне получить список всех возможных комбинаций/перестановок ящиков, которые могут предоставить мне нужные мне буквы?
Алгоритм также должен создавать комбинации ящиков для удовлетворения моих требований. Например: скажем, в Box-1 есть только 4 As, в Box-2 есть 1 A, а в Box-3 есть 1 A. Мне нужен результат алгоритма, чтобы указать, что 6 As могут быть выполнены для 3 блоков.
Какова основная логика решения такой задачи. Есть ли какие-то конкретные алгоритмы, которые мне нужно изучить для этого?
ИЗМЕНИТЬ 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.
}
}