Решение задачи 15.
Будем считать, что вектор С определяет веса элементов, а вектор В - стоимость.
Обозначим через F[k,y] величину наибольшей суммарной стоимости элементов с номерами не большими k, суммарный вес которых не превышает y. Покажем, как можно вычислить значение F[k+1,y], используя величины с меньшими значениями индексов.
Понятно, что величина F[k+1,y] может соответствовать множеству элементов, которое содержит или не содержит элемент k+1. Если множество не содержит элемент k+1, то F[k+1,y]=F[k,y]. Иначе F[k+1,y]=B[k+1]+F[k,y-С[k+1]], т.е. максимальная суммарная стоимость есть стоимость k+1 элемента плюс максимальная стоимость элементов с номерами не большими k, суммарный вес которых не превышает величины y-С[k+1].
Таким образом, мы имеем рекуррентную формулу вычисления величин
F[k+1,y]=max(F[k,y],B[k+1]+F[k,y-С[k+1]]).
Вычисляя последовательно элементы матрицы F, учитывая при этом, что F[0,y]=0 для любого y, и F[j,0] для любого j, получим значение F[N,A], которая является значением максимально возможной стоимости.
Для выяснения номеров элементов, вошедших в множество, достаточно, начав с элемента с индексами [i,y] (которые вначале равны N и A соответственно),сравнить его со значением F[i-1,y]. Если значения равны, то i элемент не входит в множество, а процесс повторяется для элемента с индексами [i-1,y]. В случае неравенства элементов элемент i входит в множество, а процесс повторяется для элемента с индексами [i-1,y-C[i]]. Процесс выполняется для всех i от N до1.
|
