Задача о рюкзаке

Когда мы решаем задачу, то, естественно, нам хотелось
бы решить ее сразу и всю и, желательно, в одно действие. Но,
к сожалению, это не всегда получается. В этом случае нам
приходится разбивать поставленную задачу на некоторые част-
ные подзадачи, и только после их решения мы можем найти ре-
шение всей задачи. Рассмотрим один из достаточно общих и по-
лезных методов того, как это можно сделать.
Сначала введем некоторые определения, которые понадо-
бятся нам в дальнейшем.
Мы будем называть 1 параметрами 0 задачи входные данные,
необходимые для ее решения.
Например, если мы решаем задачу нахождения корней квад-
ратного уравнения ax 52 0+bx+c=0, то эта задача определяется
тремя параметрами — коэффициентами а, b и c.
Если же мы хотим решить задачу сортировки некоторого
набора чисел, то параметрами задачи будут количество чисел и
их значения.
При таком подходе любая задача может быть формализована
в виде некоторой функции, аргументами которой могут являться
такие величины, как:
— количество параметров;
— значения параметров.
После того, как задача формализована в виде функции с
некоторыми аргументами, определим понятие подзадачи. Под
1подзадачей 0 мы будем понимать ту же задачу, но с меньшим чис-
лом параметров или задачу с тем же числом параметров, но ко-
торые имеют меньшие значения.
Особо хочется отметить, что под подзадачей не следует
понимать некоторые этапы решения задачи, такие, как органи-
зация ввода и вывода данных или некоторая последовательность
их обработки. Здесь речь пока идет не о способе решения за-
дачи, а о понимании задачи и подзадачи как некоторых функ-
ций, зависящих от входных параметров.
Вернемся к описанию предлагаемого метода решения задач,
суть которого состоит в следующем:
Обычно решение задачи при малых значениях параметров не
представляет особой проблемы. Например, если требуется найти
произведение всех элементов последовательности A, состоящей
из N элементов, то при N=1 произведение и будет равно этому
единственному элементу последовательности A 41 0.
Если же задача имеет большое количество параметров, то
можно попытаться свести исходную задачу к решению одной или
нескольких подзадач. Так как у подзадачи меньше число пара-
метров или эти параметры имеют меньшие значения, то через
некоторое количество таких сведений мы получим подзадачу с
малым значением параметров, которую мы, по предположению,
умеем решать. После чего останется только на основе решенных
подзадач найти решение исходной задачи.
Например, если в сформулированной выше задаче N>1, то
мы можем заметить следующее:
Для нахождения произведения первых N элементов доста-
точно знать произведение первых (N-1)-го элементов и значе-

— 2 —

ние N-го элемента.
Пусть функция Р(N) соответствует решению исходной зада-
чи. В данном случае у функции только один аргумент — коли-
чество элементов. Поэтому решение исходной задачи можно за-
писать в виде соотношения
Р(N)=Р(N-1)*A 4N. 0
Это соотношение может быть определено для любого i,
2<=i<=N: Р(i)=Р(i-1)*A 4i 0 и Р(1)=A 41 0. Приведем алгоритм. P[1]:=A[1]; нц для i от 2 до N ? P[i]:=P[i-1]*A[i] кц Это же соотношение для нахождения P[N] можно реализо- вать и без использования таблицы P: P:=A[1]; нц для i от 2 до N ? P:=P*A[i] кц Решение рассмотренной задачи, используя предлагаемый метод сведения к подзадачам, кажется очень простым. Правда, может возникнуть вопрос: "А ради чего стоило все так услож- нять, если и так было очевидно, что требуется делать?" Дело в том, что использование метода лучше всего расс- матривать именно на элементарных примерах. А затем, когда мы научимся применять его к простым задачам, то и "трудная за- дача, требующая творческого озарения, превращается в рутин- ную, решаемую стандартным путем" (Я.Н.Зайдельман). Итак, для решения некоторых задач нам необходимо снача- ла найти решения этой задачи с меньшими аргументами. Обладая этой информацией, мы можем найти решение поставленной зада- чи. Именно таким способом мы и действовали в задаче про счастливые билеты (см. предыдущий номер), где нам для нахож- дения количества N-значных "счастливых" билетов надо было сначала найти количество (N-1)-значных "счастливых" билетов. Рассмотрим описанный метод на примере следующей извест- ной задачи: Имеется N неделимых предметов. Для каждого предмета из- вестна его стоимость (в рублях) и масса (в кг.). Величины стоимости и массы являются натуральными числами. Ваша цель состоит в том, чтобы определить максимальную суммарную стои- мость предметов, которые вы можете унести в рюкзаке при ус- ловии, что суммарная масса предметов не должна превышать S кг. Рассмотрим решение задачи на примере. Положим N=5 и S=16. Пусть элемент C 4i 0 таблицы C соответствует стоимости i-го - 3 - предмета, а элемент M 4i 0 таблицы M - массе i-го предмета. Бу- дем считать, что предметы пронумерованы в порядке их следо- вания в таблицах. Пусть Т обозначает функцию, значение которой соответс- твует решению нашей задачи. Аргументами у этой функции явля- ется количество предметов, их стоимости и массы, а также максимальная суммарная масса, которую можно унести. Для нашей задачи Т(5,16) определим подзадачи Т(i,j), где i обозначает количество начальных предметов, из которых можно осуществлять выбор, а j определяет максимально возмож- ную суммарную массу уносимых предметов. Отметим, что опреде- ленный таким образом первый параметр i определяет как коли- чество предметов для подзадачи, так и значения их стоимостей и масс, определяемых из таблиц C и M. Определим сначала начальные значения функции T. Понят- но, что при нулевых значениях одного из аргументов значение функции равно 0: T(0,0)=0 T(0,j)=0 при j>0,
T(i,0)=0 при i>0.
Определим возможные значения функции T(i,j) при ненуле-
вых значениях аргументов.
Решение подзадачи, соответствующей функции T(i,j) может
быть сведено к двум возможностям: уносится ли при наилучшем
решении предмет с номером i или нет.
Если предмет не уносится, то решение задачи с i предме-
тами сводится к решению подзадачи с i-1 предметами, т.е.
T(i,j)=T(i-1,j).
Если предмет c номером i уносится, то это уменьшает
максимально возможную суммарную массу для i-1 первых предме-
тов на величину M(i), одновременно при этом увеличивая зна-
чение решения для оставшихся предметов T(i-1,j-M(i)) на ве-
личину C(i), т.е.
T(i,j)=T(i-1,j-M(i))+C(i).
При этом необходимо учитывать, что вторая ситуация воз-
можна только тогда, когда масса i-го предмета не больше зна-
чения j.
Теперь для получения наилучшего решения нам необходимо
выбрать лучшую из этих двух возможностей (уносить или не
уносить i-й предмет). Поэтому соотношение для вычисления
T(i,j) при i>0 и j>0 имеет вид
T(i,j)= max(T(i-1,j-M(i))+C(i),T(i-1,j)) при j>=M(i)
и
T(i,j)= T(i-1,j) при j=M[i]
? ? ? то
? ? ? T[i,j]=max(T[i-1,j],T[i-1,j-M[i]]+C[i])
? ? ? иначе
? ? ? T[i,j]=T[i-1,j]
? ? все
? кц
кц

Вопросы для размышления:

1. Подумайте, как по полученной таблице T определить,
какие предметы надо уносить.
2. В чем Вы видите недостаток предлагаемого алгоритма
(рассмотрите, как растет размер таблицы T в зависимости от
параметров задачи).
3. Рассмотрим еще один алгоритм. Найдем стоимость p 4i
одного килограмма каждого предмета, p 4i 0=C 4i 0/M 4i 0. Отсортируем
последовательность {p 4i 0} по невозрастанию. Из соображений
здравого смысла заключаем, что выгоднее всего сначала загру-
зить в рюкзак помещающийся туда предмет с максимальным p 4i 0.
Затем, если рюкзак не полон, то среди оставшихся предметов
опять ищем предмет с максимальным p 4i 0, который можно помес-
тить в рюкзак, и так далее.
Приводит ли этот алгоритм к решению поставленной задачи
о рюкзаке? Если да, то докажите это, если нет — приведите
пример массивов M и C, для которых алгоритм не дает опти-
мальной стоимости.

И. Волков, В. Котов, А. Лапо

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>