Метод перебора упаковки в корзину

Обратите внимание, что bin-packing — это NP-сложная проблема, в основном означающая, что для ее решения потребуется слишком много времени. использовать грубую силу даже для относительно небольших входных данных, поэтому грубая сила для NP-сложных задач почти никогда не бывает хорошей идеей. Ссылка выше показывает некоторые альтернативы (или приближения). Но я продолжу...

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

Основная идея: (для 3 предметов, 2 корзины, при условии, что все подходит, если он просто не пропускает эту ветку)

Put the first item in the first bin.
  Put the second item in the first bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the first bin and put it into the second bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the second bin.
Remove the first item from the first bin and put it into the second bin.
  Put the second item in the first bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the first bin and put it into the second bin.
    Put the third item in the first bin.
      Woo-hoo! We have a solution!
    Remove the third item from the first bin and put it into the second bin.
      Woo-hoo! We have a solution!
    Remove the third item from the second bin.
  Remove the second item from the second bin.
Remove the first item from the second bin.

(Смотрите, сколько там уже ступенек? И это только на 3 предмета и 2 корзины)

Псевдокод:

recurse(int itemID)
  if pastLastItem(itemID)
    if betterThanBestSolution
      bestSolution = currentAssignment
    return
  for each bin i:
    putIntoBin(itemID, i)
    recurse(itemID+1)
    removeFromBin(itemID, i)

Брутфорс просто пробует каждую комбинацию.

Чтобы написать код для грубой силы, рассмотрите этот прием: предположим, мы хотим посетить все комбинации 8 ферзей без жесткого кодирования 8 вложенных циклов. Просто подумайте о следующем восьмеричном числе, состоящем из 8 нулей.

00000000

Затем напишите один цикл, увеличивающий его в восьмеричной системе счисления:

00000001
00000002
00000003
...
00000007 // 7 + 1 = 10
00000010
00000011
00000012
...
77777776
77777777

Это пробует все комбинации без необходимости жестко кодировать 8 внутренних циклов. Замените 8 на n, и тот же код по-прежнему будет работать.

Вы, очевидно, можете добиться большего, чем просто грубая сила. Сначала вы вычисляете минимальное количество бункеров. Если у вас есть ячейки размером 100 и элементы с общим размером 1234, то они не поместятся в 12 ячеек, но могут поместиться в 13.

С 13 ячейками у вас будет неиспользуемое пространство 66 (1300 - 1234). Поскольку 5 x 13 = 65, должен быть хотя бы один неиспользуемый бин размером 6. Таким образом, если у вас есть какие-либо предметы размером 6 или меньше, вы можете не учитывать их в расчетах, потому что вы все равно можете вместить их в конце (конечно, вам нужно свериться с фактическими номерами, которые у вас есть, но в любом случае мелкие предметы могут быть удален из поиска).

Если два предмета точно заполняют корзину, вам не нужно рассматривать какое-либо решение, если они не подходят друг другу.

С этого момента вы используете динамическое программирование, за исключением того, что вы всегда используете самый большой неиспользуемый элемент в качестве первого элемента в новой корзине, вы всегда заполняете корзину элементами в порядке убывания, вы всегда добавляете новые элементы, пока ничего не подходит, вы никогда не рассматриваете комбинации, где все предметы меньше или того же размера, что и в другой комбинации. И, наконец, когда вы нашли комбинацию, которая соответствует минимальному количеству требуемых бункеров, вы нашли оптимальное решение.