Комментарии 8
patterns = [[0, 0, 0, 1],
[0, 0, 1, 0],
[1, 0, 1, 0],
[0, 1, 0, 0],
[0, 2, 0, 0],
[1, 1, 0, 0],
[1, 0, 0, 0],
[2, 0, 0, 0],
[3, 0, 0, 0]]
Вот это вот кошмар, не делайте так. Посчитайте, а не руками вбивайте с потенциальными ошибками.
RAWS_WIDTH = 10
order_sizes = [3, 5, 6, 9]
При таких условиях решение ищется тривиально - из рулона шириной 10 вырезается полоса шириной 9 и остаток при отсутствии заказа на полосу шириной 1 идет в расход, далее 6 и остаток используется для полосы шириной 3 и т.п.
Сумма всех выполненных разрезов по паттернам должна быть больше, чем
Тем не менее, в формуле написано "не меньше,чем". Это разные вещи, вообще-то
Я понимаю, если цель стоит получить ровно рулонов на заказы. Но если стоит "не меньше", то зачем нужны бесполезные паттерны?
Ну просто паттерн "3" как и "3 3" не нужны же,например
Например, у нас есть, один заказ размера 3. Тогда нам нет смысла разрезать по паттерну на части 3+3+3, так как нам хватит всего одного обрезка 3. То есть в общем случае задачи, такие ситуации могут появляться. Важно отметить, что это все-таки алгоритм, а не эвристика и должен работать при всех вариантах разнообразия входных данных.
Чуть добавлю про количество разбиений (речь идет не про разбиения исходных рулонов на части различных типов заказов, а будет идти о натуральных числах, но по аналогии можно понять связь между ними): Недавно посмотрел фильм про индийского математика Сриниваса Рамануджана, который изучал разбиения натуральных чисел. Фильм советую, масштаб количества разбиений можно оценить по ссылке.
Я к тому, что скорость решения зависит от числа паттернов. И все "бесполезные" паттерны только замедляют решение. Они нужны если задача минимизировать не только число болванок но и число резов -- но тогда надо стоимость каждому из паттернов назначить.
В приведенной задаче только 5 из 9 паттернов действительно нужны для поиска решения.
Метод генерации столбцов для решения задач математической оптимизации большой размерности