Мне поручили решить задачу, которая, на первый взгляд, кажется чем-то вроде обобщенной задачи присваивания (подмножество задач комбинаторной оптимизации: http://en.wikipedia.org/wiki/Generalized_assignment_problem).
Описание проблемы довольно непонятное и написано не на английском языке; пожалуйста, потерпите меня, поскольку я пытаюсь объяснить это как можно лучше:
Мне дается набор «разрезов» (заданий), которые нужно выполнить на больших мраморных блоках определенных размеров. Цель состоит в том, чтобы выполнить все задачи в заданном списке, сводя к минимуму количество потерянного мрамора. Если у меня есть, например, начальный блок размера 20, то я могу разрезать его по-разному, чтобы выполнить определенное количество задач, при этом следя за тем, чтобы не «потерять» мрамор в процессе. Если мне нужны подблоки из 3, 5, 6 и 6, то блок начального размера 20 вполне подойдет, так как у меня не будет потерянных шариков (3+5+6+6 = 20).
Таким образом, цель состоит в том, чтобы выполнить все задачи, потеряв при этом как можно меньше мрамора. Я могу использовать любое количество стартовых блоков, если все задачи выполнены. Одно дополнительное ограничение заключается в том, что каждой задаче, определяющей подблок длины L, также назначается «класс», который представляет, какая конкретная машина требуется для выполнения этого конкретного разреза. Имея начальный блок, я не могу использовать более 3 разных классов, чтобы разрезать свой блок. Я могу сделать столько разрезов, сколько захочу, на одной машине, если я не меняю класс более двух раз.
Вот пример данных, которые могут быть предоставлены мне:
2 20 38
7
20
4 1
7 1
3 1
25 1
22 2
22 1
20 2
17 1
10 1
22 2
27 2
26 2
15 3
13 4
12 5
15 6
27 4
27 5
27 7
27 2
В первой строке указано количество различных блоков, которые можно использовать для выполнения всех заданных задач, а также размеры каждого начального блока.
Во второй строке указано общее количество различных «классов» разрезов, которые представляют собой количество различных машин, которые могут выполнять необходимые разрезы.
В третьей строке указано общее количество разрезов (задач), необходимых для выполнения операции. В этом случае для решения задачи необходимо выполнить ровно 20 заданий.
Остальные строки дают необходимый разрез, а также класс, связанный с этой задачей.
Подводя итог, мне нужно выполнить определенный список задач с любым количеством заданных начальных блоков, пытаясь свести к минимуму количество потерянных/ненужных шариков.
Итак, мой вопрос: Каков хороший подход к этой проблеме? Я считаю, что жадный алгоритм аппроксимации может быть прямым и простым способом найти разумное решение, но я, честно говоря, не уверен.
Заранее извиняюсь, если данная проблема неясна, если вам нужна дополнительная информация, не стесняйтесь запрашивать более четкие инструкции.
Спасибо!
PS: Алгоритм будет написан на Java, если это поможет.
