В этой статье объясняется, как рекуррентное соотношение 0/1 Knapsack можно преобразовать в код динамического программирования сверху вниз. Если вы хотите понять, как мы пришли к представленному ниже рекуррентному соотношению, пожалуйста, прочитайте статью Выявление и подход к проблеме динамического программирования.

Чтобы написать код для любого рекурсивного отношения, мы должны сначала определить базовое условие. Лучший способ сделать это — подумать о наименьшей возможной подзадаче. В рюкзаке два базовых случая:

  1. Представьте, что у сумки нет вместимости (или нулевой вместимости). Это означает, что сумка не может содержать никаких предметов, даже если есть предметы, которые мы можем добавить в сумку. Таким образом, максимальная прибыль всегда равна нулю. Математически мы представляем это как F (N, 0) = 0.
  2. Точно так же представьте, что нет предметов для добавления в мешок, тогда, независимо от вместимости мешка, прибыль всегда будет равна нулю, потому что в мешок нечего добавлять, т. е. F (0, C) = 0.

Теперь давайте подойдем к заключительной части решения, то есть к написанию таблицы для восходящего подхода динамического программирования. В этой задаче у нас есть две переменные: вместимость мешка «C» и количество предметов «N». Таким образом, нам нужно построить таблицу размера T [N + 1][C + 1], как показано ниже. Любая произвольная ячейка T[i][j] в таблице дает максимальную прибыль при выборе из i предметов в мешок вместимостью j. Таким образом, конечным результатом, который нам нужен, является T[N][C], который дает максимальную прибыль, выбирая из «N» предметов в мешок вместимостью «C».

Рекуррентное соотношение и базовое условие можно переписать с использованием переменных «i» и «j», как показано ниже, путем простой замены «N» на «i» и «C» на «j».

Теперь давайте посмотрим, как заполнить таблицу, используя базовое условие и рекуррентное отношение выше.

Остальные ячейки в таблице можно заполнить, используя рекуррентное отношение, как показано ниже.

Для полной реализации перейдите в Репозиторий GitHub

В следующей статье я покажу вам, как решать другие задачи динамического программирования, подобные задаче о рюкзаке 0/1.