значениях одного
значениях одного из аргументов значение функции равны:
T(0,j)=0 при j?1, {нельзя без предметов набрать массу j>0}
T(i,0)=0 при i?1. {всегда можно набрать нулевую массу }
Определим возможные значения функции 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,j)=T(i-1,j-M[i]).
При этом необходимо учитывать, что вторая ситуация возможна только тогда, когда масса i-го предмета не больше значения j.
Теперь для получения решения нам необходимо выбрать лучшую из этих двух возможностей. Поэтому рекуррентное соотношение при i?и j?1 имеет вид:
T(i,j)=T(i-1,j) при j<M[i];
T(i,j)=max(T(i-1,j),T(i-1,j-M[i]))
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
