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