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

Question

Я пытаюсь вкладывать материал с наименьшими потерями или отходами.

Table A

Qty Type Description Length

2   W    16x19       16'
3   W    16x19       12'
5   W    16x19       5'
2   W    5x9         3'


Table B

Type Description StockLength

W    16X19       20'
W    16X19       25'
W    16X19       40'
W    5X9         20'

Я просмотрел алгоритмы Greedy, Bin Packing, Knapsack, 1D-CSP, разветвление и связывание,Грубая сила и другие.Я почти уверен, что это проблема режущего материала.Мне просто нужна помощь, чтобы придумать функцию (ы), чтобы запустить это.У меня не одна длина запаса, а несколько, и пользователь может ввести свой собственный инвентарь менее распространенных длин.Будем весьма благодарны за любую помощь в определении функции или алгоритма, который будет использоваться в PHP для создания оптимизированного шаблона резки и длины заготовок, необходимых с наименьшими затратами.

Спасибо

Answer 1

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

Если ваш вопрос «дай мне алгоритм», я боюсь, что вы ищете ответ не в том месте.Это сайт, ориентированный на технологию , а не ориентированный на алгоритмы.Несмотря на то, что мы, программисты, конечно, понимаем алгоритмы (например, почему неэффективно передавать одну и ту же строку в strlen на каждой итерации цикла, или почему пузырьковая сортировка не подходит, за исключением очень коротких списков), большинство вопросов здесьнапример, «как мне использовать API X с использованием языка / фреймворка Y?».

Чтобы ответить на сложные вопросы алгоритма, подобные этому, требуется определенный опыт (включая, помимо прочего, множество математических способностей).Люди в области исследования операций работали над такими проблемами больше, чем большинство из нас когда-либо.Вот вводная книга по теме.

Как инженер, пытающийся найти практическое решение реальной проблемы, я сначала получил бы ответы на эти вопросы:

• Насколько велик средний экземпляр проблемы, которую вы пытаетесь решить? Поскольку ваша общая проблема является NP-полной (как уже сказал Джитамаро), для умеренно больших проблемных примеров необходимо использоватьэвристики.Если вы собираетесь решать только небольшие проблемы, возможно, вам удастся реализовать алгоритм, который находит оптимальный оптимум, но, конечно, вам придется предупредить пользователей, что им не следует использовать ваше программное обеспечение для решения больших проблем..

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

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

• Сколько ваши клиенты готовы платить за высокуюкачественное решение? В отличие от базы данных или веб-программирования, которое может сделать практически каждый, потому что алгоритмы сведены к минимуму (например, вы редко кодируете точную процедуру, с помощью которой база данных SQL предоставляет результат запроса), исследование операцийтребует как математических, так и инженерных навыков.Если вы не берете плату за них, вы теряете деньги.

Answer 2

Это выглядит как вариант 1-мерной упаковки. Вы можете попробовать наилучшим образом подойти, а затем попробовать с другой сортировкой таблицы б. Во всяком случае, не существует решения в 3/2 оптимального и потому, что это NP-полная проблема. Вот хороший урок: http://m.developerfusion.com/article/5540/bin-packing. Я много использовал для решения своей проблемы.