Bin упаковка bruteforce метод

Question

Мне нужно сделать программу, которая решает проблему упаковки корзины, но я уже сделал первые подходящие и жадные алгоритмы, но мой лектор говорит, что в некоторых случаях он не найдет минимального решения проблемы. Поэтому я решил попробовать bruteforce, но я понятия не имею, как он должен проверять все возможные решения. Так что да ... может кто-нибудь объяснить мне или дать псевдокод или что-то в этом роде. Я был бы очень признателен.

Answer 1

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

Recursion делает грубую силу легкой. После того, как вы понимаете a basic recursive algorithm, продолжайте читать ...

Основная идея: (для 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) 

Answer 2

Грубая сила просто пробует любую комбинацию.

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

00000000 

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

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

, который пытается все комбинации, без необходимости жесткого кода 8 внутренних циклов. Замените 8 на n, и тот же код все еще работает.

Answer 3

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

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

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

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