Режущий материал algo - C# реализация

Question

Я ищу решение или алгоритм C# для Cutting Stock Problem. Мое требование, как показано ниже:

1. я получить лист сказать 1000 * 1000 (Ш *)
2. мне нужно разрезать его на 3 части 150 * 200, 300 * 250, 275 * 300
3. Мне нужно найти оптимальное решение для максимизации количества разреза вдоль этих линий, т. Е. Потери должны быть минимальными, а количество должно быть максимально !!!

Любые указатели или ссылки на любой файл C# были бы очень полезными.

P.S: Я искал предыдущие вопросы, касающиеся этой проблемы, и я не нашел никакого кода C# или каких-либо алгоритмических шагов, чтобы преобразовать его в код C#.

Answer 1

Режущий материал Проблема - проблема с NP. Невозможно достичь гарантированного оптимального решения в разумные сроки.

Как ссылка, которую вы указали, метод Gilmore и Gomory можно применять, если вас не беспокоят целые решения (1,2 части прямоугольника 1-го типа).

В противном случае вы можете рассмотреть множество эвристик, доступных в Интернете. Ниже ссылка для алгоритмов упаковки в контейнерах 2D: How is 2D bin packing achieved programmatically?

Примечания: Существует тонкое, но важное различие между режущими проблемами запасов и проблемами упаковкой в ​​контейнерах. Вам придется соответствующим образом адаптировать алгоритм.