Проблема режущего материала

Question

Кто-нибудь знает, как реализовать алгоритм для этой задачи с использованием алгоритма рюкзака?

Метод, который я использую в настоящее время, широко использует LINQ и Collections of Collections и несколько словарей. Для тех, кто не знает, о чем я говорю, посмотрите The Cutting Stock Problem.

Answer 1

Как упомянуто в данной ссылке, эта проблема фактически является экземпляром ILP , который обычно NP-hard.

Непосредственно из Википедии: Расширенные алгоритмы для решения целочисленных линейных программ включают в себя:

• метод плоскости резки
• ветвь и граница
• ветвь и срез