Для хранения исходных данных задачи определим двухмерный массив f с нумерацией строк от 1 до n и нумерацией столбцов от 0 до a. Пусть f[k, x] —прибыль предприятия k при условии, что ему выделяют x млн усл. ед.
Определим двухмерные массивы F и Y с нумерацией строк от 1 до n и нумерацией столбцов от 0 до a:
F[k, x] — наибольшая прибыль, которую можно получить, разделив x млн усл. ед. между первыми k предприятиями; Y[k, x] — сумма, которая выделяется предприятию k.
Первоначально F[k, x] = f [1, x] и Y[k, x] = x для всех x:
Основная программа состоит из вложенных циклов:
На каждом шаге внешнего цикла сравниваются значения F[k–1, x–y] + f[k, y], вычисленные для всех y от 0 до x, и для F[k, x] берется большее из них. Для Y[k, x] берется соответствующее значение y.
В результате выполнения программы имеем:
Из первой таблицы берем значение F[n, a] = 1,4 — это наибольшая прибыль, которую можно получить, разделив 8 млн усл. ед. между тремя предприятиями:
Обратный проход по второй таблице, начиная с Y[n, a], дает возможность выяснить, какие денежные средства были вложены в каждое предприятие.
Для запоминания этой информации потребуется массив P с нумерацией элементов от 1 до n. Определим P[k] как количество денег, которые выделяются предприятию k, при условии оптимального распределения всех средств.
Программа может быть записана так:
На каждом шаге цикла мы переходим от значения Y[k+1, x] к значению Y[k, x–Y[k+1, x]], k = n–1, …, 1.
Итак, первому заводу выделяем 3 млн усл. ед. из восьми, второму — 2, третьему — 3 млн усл. ед.
В заключение заметим, что при вычислении значений Fk(x), 0 ≤ x ≤ a, определяемых по формуле (10.4), можно держать в памяти лишь две последовательные строки массива F, поскольку нужны только значения Fk–1(y), 0 ≤ y ≤ x.
Задача о рюкзаке
Ситуация 3.Вы собираетесь в поход, и возникает вопрос: «Что взять с собой?». Хотелось бы взять больше: мало ли что понадобится в пути. Однако все это придется нести на себе, а чем тяжелее рюкзак, тем труднее идти. Конечно, в походе нельзя обойтись без палатки, спального мешка, посуды, но многие другие вещи взаимозаменяемы и не являются предметами первой необходимости.
Построим математическую модель этой ситуации.
Пусть имеются предметы n видов. Каждый предметвида i имеет массу ai и условную стоимость (ценность) сi, i = 1, 2, …, n. Договоримся, что масса рюкзака не должна превышать b кг. Условимся также, что все заданные параметры — неотрицательные целые числа.
Задача состоит в том, чтобы загрузить рюкзак предметами, суммарная стоимость которых была бы наибольшей.
Предположим, что мы положили в рюкзак хi единицпредметов вида i. Тогда его масса равна сумме
a1х1 + a2х2+ … + anхn.
Стоимость выбранных предметов равна
с1x1+ c2x2 + … + cnхn.
Стоимость предметов должна быть как можно больше, а масса рюкзака ограничена значением b. Поэтому математическая модель ситуации выглядит так:
Z = с1x1+ c2x2+ … + cn хn → max,
a1х1 + a2х2+ … + anхn ≤ b;
xi — неотрицательные целые числа,1 i n.
Полученную задачу называют задачей о рюкзаке. Как найти алгоритм ее решения?
Введем обозначение: Zk(х) –– наибольшая суммарная стоимость набора предметов вида 1, 2, …, k при условии, что их масса не превышает значения x.
Последовательно найдем Z1(х)для х = 0,1,…, b,затем Z2(х) для тех же х и т. д. Закончим вычислением значения Zn(b), которое дает оптимальное решение задачи. Это означает, что сначала мы заполняем рюкзак предметами только первого вида, затем первого и второго, далее первого, второго и третьего вида и т. д. Вначале масса рюкзака берется равной 1 кг, затем — 2, 3 и так до b кг.
Предположим, что мы уже знаем: 1) как лучше заполнить рюкзак предметами первых k – 1 видов, если его масса ограничена любым числом от 1 до b; 2) как лучше заполнить рюкзак предметами первых k видов, если его масса ограничена любым числом от 1 до х – 1. Другими словами, известны значения Zi(у) для всех i от 1 до k – 1и всех у от 1 до b,а также значения Zk(у) для всех у от 1 до х – 1. Как теперь наилучшим образом загрузить рюкзак предметами k видов, если его масса ограничена значением х, то есть, как найти Zk(х)?
У нас есть две возможности:
1) предмет k-говида не берем в рюкзак;
2) предмет k-говида берем в рюкзак (возможно там уже имеются предметы этого вида).
В первом случае рюкзак оптимально заполняется предметами первых k – 1 видов, общую стоимость которых Zk–1(х) мы знаем.
Во втором случае мы берем предметвида k, имеющий массу ak. Это уменьшает возможную массу остальных предметов в рюкзаке до значения (х – ak) и увеличивает общую стоимость предметов на величину ck. Задача оптимального заполнения рюкзака предметами первых k видов для массы (х – ak) решена, стоимость этих предметов известна и равна Zk(х – ak). Следовательно, общая стоимость предметов во втором случае определяется значением Zk(х – ak) + ck.
Теперь из двух вариантов укладки рюкзака надо выбрать лучший. Исходя из этого, выводим общую формулу:
Zk(х) = max{Zk– 1(х), Zk(х – ak) + ck}. (11.5)
Важно отметить, что значения Zk(х) можно вычислять для любых k и х, полагая, что Zk(x – ak) = – когда ak > x (т. е. масса предмета k больше вместимости рюкзака x). Ясно также, что Z0(x) = 0 (случай, когда ни один из предметов не берется) и Zk(0) = 0 (случай, когда вместимость рюкзака равна нулю).
При заполнении рюкзака, масса которого ограничена значением х,предметами только первого вида, в него помещается x1 = [x/a1] таких предметов (здесь [z] — наибольшее целое число, не превосходящее z). Поэтому значения Z1(х) вычисляют по простой формуле
Z1(х) = [x/a1]×c1, (11.6)
Для иллюстрации общих результатов рассмотрим конкретный пример. Пусть дана задача:
Z = 2x1 + 4x2 + 5x3→ max,
2x1 + 3x2 + 3x3 ≤ 8;
xi — не отрицательные целые числа,1 i 3.
Требуется найти значение Z3(8).
Прежде всего, полагаем Z0(x) = 0, Z1(0) = 0.
Согласно формуле (11.6) Z1(х) = [x/2]×2. В данном случае
Здесь мы получаем максимум, когда берем предмет второго вида, масса которого равна 3.
Для x = 4 находим
Z2(4) = max {Z1(4), Z2(4 – 3) + 4} = max {4, 0 + 4} = 4.
На это раз при выборе максимума имеются два равных значения. Возможны варианты: 1) когда мы берем предмет второго вида, и 2) когда берутся предметы только первого вида.
Действуя аналогично, вычисляем и помещаем в таблицу значения Z2(х) для x = 5, 6, 7, 8:
x
Z0(x)
Z1(x)
Z2(x)
Z3(х) вычисляем по формуле
Z3(х) = max{Z2(х), Z3(х – 3) + 5}.
Расчеты ведем по тем же правилам. В итоге получаем таблицу:
x
Z0(x)
Z1(x)
Z2(x)
Z3(x)
В этой таблице содержатся оптимальные решения задачи для всех значений x от 0 до 8. Для x = 8 стоимость выбранных предметов Z3(8) = 12 усл. ед.
Чтобы указать набор предметов, которые мы берем в рюкзак, необходимо сделать обратный проход по таблице, начиная с Zn(b) и заканчивая Z1(x).
Обозначим через Х = (х1, х2, …, хn) набор предметов при оптимальной загрузке рюкзака. Здесь xi ≥ 0 — количество предметов вида i. Построение Х производим в обратном порядке: последний предмет, который берем в рюкзак, будет учтен первым, а предметы, попавшие туда первыми, будут учтены в последнюю очередь. Вначале полагаем, что Х = (0, 0, …, 0).
Напомним, что
Zn(b) = max{Zn–1(b), Zn(b – an) + cn}.
Если Zn(b) = Zn–1(b), то предмет вида n не попал в рюкзак, и набор Х по-прежнему нулевой. Далее нужно проанализировать способ вычисления Zn–1(b).
Если же Zn(b) = Zn(b – an) + cn, то предмет вида n попал в рюкзак, поэтому набор (0, 0, …, 0) заменяем на (0, 0, …, 1). Далее нужно проанализировать способ вычисления Zn(b – an).
Аналогично поступаем на промежуточном шаге построения Х.
Пусть нужно проанализировать способ вычисления Zk(x). Если Zk(х) = Zk–1(х), то переходим к значению Zk–1(х), а набор Х оставляем прежним. Если же Zk(х) = Zk(х – ak), то переходим к значению Zk(х – ak), в этом случае набор (0, …, хk, … хn) заменяем на (0, …, хk+1, … хn).
На последнем шаге учитываем способ вычисления Z1(х) = [x/a1]×c1. Значение [x/a1] –– число предметов первого вида, попавших в рюкзак. Поэтому набор (0, х2, …, хn) заменяем на ([x/a1], х2, …, хn).
Вернемся к условиям нашей задачи.
Вначале Х = (0, 0, 0).
Z3(8) = max{Z2(8), Z3(8 – 3) + 5} = max{ Z2(8), Z3(5) + 5} = max{10, 7 + 5} = 12. Поэтому Z3(8) = Z3(5) + 5. Набор (0, 0, 0) заменяем на (0, 0, 1) и переходим к значению Z3(5).
Z3(5) = max{Z2(5), Z3(5 – 3) + 5} = max{Z2(5), Z3(2) + 5} = max{6, 2 + 5} = 7. Поэтому Z3(5) = Z3(2) + 5. Набор (0, 0, 1) заменяем на (0, 0, 2) и переходим к значению Z3(2).
Z3(2) = max{Z2(2), Z3(2 – 3) + 5} = max{Z2(2), Z3(–1) + 5} = max{2, –∞ + 5} = 2. Поэтому Z3(2) = Z2(2). Набор Х остается прежним, переходим к значению Z2(2).
Z2(2) = max{Z1(2), Z2(2 – 3) + 4} = max{Z1(2), Z2( –1) + 4} = max{2, –∞ + 4} = 2. Поэтому Z2(2) = Z1(2). Набор Х остается прежним, переходим к значению Z1(2).
Z1(2) = [2/2]×2 = 2. Так как [2/2] = 1, в рюкзак попадает только один предмет первого вида. Окончательно Х = (1, 0, 2).
Таким образом, для оптимальной загрузки рюкзака берем один предмет первого и два предмета третьего вида.
Можно было заметить с самого начала, что брать предметы второго вида нерационально, поскольку при равной массе с предметами третьего вида они имеют меньшую ценность.
Отметим, что наборы Х = (х1, х2, …, хn) можно было записывать одновременно с вычислением значений Zk(х).
