Здравствуйте!
Мне нужно решить вариант задачи о рюкзаке.
Вот неформальная постановка задачи.
Имеется склад с пронумерованными ячейками, в которых лежат различные товары. Один товар может лежать в нескольких ячейках.
Пример содержимого склада:
Ячейка №1 - Товар №1 - 6 коробок по 500 шт.
Ячейка №1 - Товар №2 - 5 коробок по 300 шт.
Ячейка №1 - Товар №3 - 3 коробки по 200 шт.
Ячейка №2 - Товар №2 - 1 коробка по 300 шт.
Ячейка №2 - Товар №2 - 2 коробки по 200 шт.
Ячейка №2 - Товар №3 - 1 коробка по 300 шт.
Ячейка №3 - Товар №1 - 4 коробки по 300 шт.
Ячейка №3 - Товар №3 - 2 коробки по 200 шт.
Ячейка №3 - Товар №3 - 3 коробки по 300 шт.
...
Есть список товара, который нужно выгрузить. Список состоит из нескольких позиций (позиция = вид товара + количество штук).
Пример списка:
Товар №1 - 2840 шт.
Товар №2 - 3130 шт.
Товар №3 - 700 шт.
...
Задача: оптимальным образом выгрузить всю продукцию по списку.
Критерии оптимальности следующие:
1. Число использованных ячеек (для списка в целом) должно быть минимальным.
2. Точность подбора по количеству штук должна быть максимальной.
Критерии применяются по порядку: сначала критерий №1, затем критерий №2.
Если бы не было критерия №1, это была бы классическая задача о рюкзаке с возможностью единичного выбора предмета. Решение этой задачи динамическим программированием приведено здесь:
http://ru.wikipedia.org/wiki/Задача_о_ранце.
Проблема в том, как минимизировать число использованных ячеек для всего списка. Можно, конечно, сначала найти все минимальные наборы ячеек, содержащие всю продукцию по списку (например, {Ячейка №1, Ячейка №7} или {Ячейка №2, Ячейка №5}), и затем для каждого набора решить задачу о рюкзаке с подбором по количеству. Но, боюсь, что такое решение будет работать долго.
Может быть, можно рекуррентные соотношения, приведенные в этой статье (
http://ru.wikipedia.org/wiki/Задача_о_ранце), модифицировать так, чтобы находилось решение, оптимальное в первую очередь по количеству ячеек (для списка в целом), а затем по количеству штук?
Я затрудняюсь найти такое рекуррентное соотношение. Может быть, вы поможете найти его, или подскажете другой эффективный алгоритм решения задачи?
