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

Скажем, есть 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.
    }
}

person StackOverflowNewbie    schedule 20.11.2010    source источник
comment
Не могли бы вы предоставить некоторые сведения? Зачем тебе ВСЕ комбинации? Это не кажется полезным, так как после перечисления случаев у вас нет критерия для выбора. Если только это не любопытство... или домашнее задание.   -  person Dr. belisarius    schedule 20.11.2010
comment
@belisarius: для выбора не обязательно быть критерием. Возможно проблема решена со всеми выявленными комбинациями. Кроме того, почему единственными двумя возможными причинами, по которым я задаю этот вопрос, должно быть любопытство или домашнее задание? Разве это не может быть реальной проблемой, над которой я работаю?   -  person StackOverflowNewbie    schedule 20.11.2010
comment
Ах, да, конечно! Поскольку это сайт обмена, я просто прошу вас поделиться наиболее публичной частью обоснования вашего вопроса, просто чтобы помочь другим понять, к какой проблеме могут быть применены полученные вами ответы. Правильные ответы: {моя проблема...}, {просто любопытство}, {не ваше дело}. Хотя последнее мало помогает.   -  person Dr. belisarius    schedule 20.11.2010


Ответы (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.
  }
}
person dcp    schedule 20.11.2010
comment
@dcp: в вашем фрагменте должны быть поля переменных? Кроме того, я не знаком с нотацией <<; что это значит? - person StackOverflowNewbie; 20.11.2010
comment
Да, ящики — это массив ящиков, и каждый элемент массива должен содержать количество букв a, b и т. д. для данного ящика. Обозначение ‹‹ сдвигается влево на 1 бит. (1‹‹n)-1 представляет все выбранные поля (поэтому, если у вас есть 10 полей, это число будет (2^n)-1. Вы можете думать о 1‹‹n и 2^n как об одном и том же, потому что они :). - person dcp; 20.11.2010
comment
Это кажется мне довольно хорошим решением только с одной небольшой возможной проблемой. Если есть ограничение, согласно которому вы должны подобрать хотя бы одну букву при посещении ящика, этот алгоритм сгенерирует перестановки, нарушающие это ограничение. Например. если вам нужно только 1x A письмо из x = 10 ящиков, это может быть точно удовлетворено, посетив любой из 10 ящиков, поскольку все они содержат по крайней мере один экземпляр каждого типа буквы... но он будет «неудовлетворен», посетив все 10 ящиков (mask=1111111111), что означает, что вы не берете письма в некоторых ящиках. - person Nathan Pitman; 20.11.2010
comment
@dcp: я попытаюсь перевести ваш код на PHP, который я использую. что, если бы я имел дело с большим количеством ящиков, скажем, с сотнями? это будет слишком медленно? мне все еще нужно применить некоторые вычисления к каждой полученной комбинации (но они довольно прямолинейны, просто некоторые основные математические вещи). - person StackOverflowNewbie; 20.11.2010
comment
@dcp: я перевел твой код на PHP. Я никогда не доходил до того, что я должен был проверить переменную tots. Я сделал что-то неправильно? - person StackOverflowNewbie; 20.11.2010
comment
Один важный вопрос SONewbie - при посещении ящика вы берете столько букв каждого типа, сколько вам нужно? Раньше я предполагал, что вы этого не сделаете. Потому что, если вы это сделаете, вы можете значительно оптимизировать этот алгоритм для большого количества ящиков. Например. если вы оцениваете маску = 1010100000 и определили, что она удовлетворяет вашим требованиям к буквам, вы можете пропустить все остальные маски в формате 10101xxxxx. - person Nathan Pitman; 20.11.2010
comment
@StackOverflowNewbie - на первый взгляд я не вижу ничего плохого в вашем коде. Можете ли вы попробовать пройти через это в отладчике? (извините, я не очень хорошо разбираюсь в синтаксисе PHP, но ваш код выглядит нормально). - person dcp; 20.11.2010