Нахождение всех возможных вариаций в задаче бин-упаковки

Question

Для моей задачи мне пришлось написать алгоритм упаковки бина, в котором есть N объектов с разными объемами. Все они должны были быть упакованы в коробки тома V. Использование уменьшающейся сортировки Я успешно написал алгоритм. Но другая задача включает в себя выписывание всех возможных вариантов упаковки для мусора в количестве коробок, которые я ранее нашел наиболее эффективными. Так, например:

Имеется 4 объекта с объемами: 4, 6, 3, 2. Объем коробок - 10. Используя алгоритм упаковки бина, я обнаружил, что мне понадобятся 2 коробочки.

Все возможные варианты будут:

4,6 and 3,2
4,3 and 6,2
4,2 and 6,3
6   and 4,3,2

У меня проблемы с поиском подходящего алгоритма для этой проблемы, с чего мне начать? Любая помощь будет принята с благодарностью.

Answer 1

Общий алгоритм решения этой проблемы выглядит следующим образом:

Попытайтесь разместить все объекты в n корзинах, создав все возможные расщепленные конфигурации в n группах ипроверьте, подходит ли какая-либо из этих конфигураций к корзинам.

Если нет, увеличьте n и повторите попытку.

Теперь, как найти все возможные разделенные конфигурации?

Рассмотрите возможность размещения тега на каждом объекте, чтобы определить, к какой корзине он принадлежит.Если у вас есть 3 объекта и 2 корзины, то каждый объект может получить тег 0 или 1 (для любой из двух корзин).Это составляет 2 ^ 3 = 8 комбинаций:

000
001
010
...

Теперь также становится понятно, как создавать все комбинации.Вы можете использовать счетчик и преобразовать его в основание количества бинов (в данном случае 2) и использовать цифры в качестве тегов.Есть и другие варианты, например, вы можете использовать рекурсивное решение.Я предпочитаю это.

Когда у вас есть решение, вам просто нужно проверить, что для каждого бина сумма объема объектов этого тега не превышает размер бина.

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

combinations(object_counter, bin_counter) {
    if (object_counter == 0) {
        return [[]]  // a list of one empty list
    }
    result = []  // empty list
    for i in 0 .. bin_counter-1 {
        sub_results = combinations(object_counter-1, bin_counter)
        for sub_result in sub_results {
            result.append([i] + sub_result)
        }
    }
    return result
}