Рис. 4.12.Пример объединения грузов.
Шаг 9) В полученном множестве подмножеств грузов большей мощности числом грузов равным осуществляем их объединение, для получения множества подмножеств грузов мощности М. Если множества подмножеств грузов мощности М будет пусто то увеличиваем Nуг на определённое значение и запоминаем. Переходим к шагу 3. Если в результате объединение получим не пустое множество грузов мощности М, то выбираем из полученного множества подмножество грузов мощности М с суммарным весом грузов больше W. Если такое подмножество грузов мощности М, с суммарным весом грузов больше или равно W, будет не найдено то увеличиваем Nуг на определённое значение и запоминаем. Переходим к шагу 3. Иначе выбираем из полученного множества подмножеств грузов мощности М подмножество грузов с суммарным весом грузов меньше или равно W и с максимальной суммарной ценой, которое и будет искомым решением задачи о ранце.
Шаг 10) Уменьшаем значение М на 1, выбираем Nуг, и запоминаем. Если М> 0 то переходим к шагу 3. Иначе переходим к шагу11.
Шаг 11) Выбираем, из полученного множества локальных подмножество грузов с максимальной суммарной ценой для различных уменьшенных значений М, подмножество грузов с максимальной суммарной ценой, который и будет локальным оптимумом решения задачи о ранце.
Индикатором нахождения искомого результата является само появление такого подмножества грузов мощности М, суммарный вес грузов которого будет больше или равен W.
Демонстрационный пример решения задачи о ранце
Для задачи о ранце определим, что ранец имеет грузоподъёмность W = 12. Количество грузов n = 5. Значения весов грузов W зададим в виде таблицы 3.
Таблица 3. Определение весов грузов
Для данного множества грузов максимальная мощность подмножеств грузов М = 3.
Согласно моего метода, для получения оптимального решения задачи о ранце, необходимо чтобы:
m = (М+1) /2 для M для нечётных;
m = M/2+1 для M для чётных.
Для данного примера задачи о ранце: М = 3, m = 2.
Значения цены грузов P зададим в виде таблицы 4.
Таблица 4. Определение цены грузов
С помощью метода неявного перебора был получен оптимальный результат для данного примера задачи о ранце:
W = W2 + W4 = 4 + 8 = 12
P = P2 + P4 = 6 + 7 = 13
Занесём определённый упорядоченный вектор грузов относительно значений весов грузов и их цены в таблицу 5.
Произведём объединение грузов из множества грузов в подмножества грузов по два и по три.
Полученные упорядоченные вектора подмножества грузов по два и по три и их значений суммарных весов грузов и цен занесём