Алгоритм расчета наиболее эффективной группировки

Question

У меня есть довольно странный вопрос на моих руках.

У меня есть список (~ 500 записей) длин деревянных балок разных размеров, таких как 3400 мм, 1245 мм, 900 мм и т. Д. Максимальная длина деревянного бруса составляет 5400 мм и для уменьшения количества Я хочу найти алгоритм, который пытается всеми возможными способами объединить меньшие размеры, чтобы поместиться в пучки 5400 мм или как можно ближе.

Так скажем, у меня есть пять различных длин: 3000, 1000, 300, 2000, 900, я бы в конечном итоге с:

• 3000 + 2000 + 300 = 5300 // Ближайшим комбинация 5400, что означает, что количество древесины, потраченной впустую, составляет всего 100 мм на этом балке.

• 1000 + 900 = 1900 // Остальные

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

Чтобы сделать вещи еще хуже

Допустим, мы находим решение вышеуказанной проблемы. Парни в магазине древесины редко поставляют пучки шириной 5400 мм, но они могут варьироваться от 3000 до 5000 с интервалом в 100 мм. Так что я получу список длин лучей из них при доставке.

Можно ли совместить список «это лучи, которые я получил» со списком «узнать наилучшую комбинацию требуемых длин лучей»?

Я не уверен, стоит ли это в конце, но любая помощь приветствуется.

Сердечные приветы Richard

Answer 1

Это в 1 размерности Cutting Stock Problem. Это сводится к Knapsack problem, так что он на самом деле NP-полностью, но он обычно сговорчив и в тех случаях, когда существует не так много хороших приближенных решений, потому что это безумно важная проблема в промышленности.

Обычно он решается именно с использованием динамического программирования, которое является своего рода умом, но вы можете найти множество примеров реализации, которые помогут вам. Приблизительные полиномиальные временные решения обычно называют код динамического программирования (который имеет псевдополиномиальную сложность) в разных точках, а окружающий код проще. Я предполагаю, что домашнее сообщение здесь не пытается написать его самостоятельно, найти чужой код и перенести его на свой язык и среду приложений.