Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 14.4 Задача о рюкзаке 0-1

Задача о рюкзаке является отличным примером для начала изучения динамического программирования и представляет собой одну из наиболее распространенных форм этой задачи. У нее существует множество вариантов, например задача о рюкзаке 0-1, задача о полном рюкзаке, задача о многократном рюкзаке и т.д.

В этом разделе сначала разберем самый распространенный вариант - задачу о рюкзаке 0-1.

Question

Даны \(n\) предметов. Вес \(i\)-го предмета равен \(wgt[i-1]\) , стоимость равна \(val[i-1]\) . Также дан рюкзак вместимости \(cap\) . Каждый предмет можно выбрать только один раз. Найдите максимальную суммарную стоимость, которую можно поместить в рюкзак при заданной вместимости.

Как видно на рисунке 14-17, поскольку номер предмета \(i\) начинается с \(1\) , а индексы массива начинаются с \(0\) , предмету \(i\) соответствуют вес \(wgt[i-1]\) и стоимость \(val[i-1]\) .

Рисунок 14-17 Пример данных для задачи о рюкзаке 0-1

Задачу о рюкзаке 0-1 можно рассматривать как процесс из \(n\) раундов принятия решений: для каждого предмета есть два решения - не класть его в рюкзак или положить в рюкзак. Поэтому задача удовлетворяет модели дерева решений.

Цель задачи - найти «максимальную суммарную стоимость при ограниченной вместимости рюкзака», а это с большой вероятностью указывает на задачу динамического программирования.

Шаг 1: продумать решения на каждом раунде, определить состояние и тем самым получить таблицу \(dp\)

Для каждого предмета возможны два случая: не класть его в рюкзак, тогда вместимость не меняется. Или положить его в рюкзак, тогда оставшаяся вместимость уменьшается. Отсюда получается определение состояния: текущий номер предмета \(i\) и текущая вместимость рюкзака \(c\) , то есть состояние обозначается как \([i, c]\) .

Подзадача, соответствующая состоянию \([i, c]\) , такова: максимальная стоимость, которую можно получить, используя первые \(i\) предметов и рюкзак вместимости \(c\). Ее решение обозначается через \(dp[i, c]\) .

Искомым значением является \(dp[n, cap]\) , значит, нам нужна двумерная таблица \(dp\) размера \((n+1) \times (cap+1)\) .

Шаг 2: найти оптимальную подструктуру и на ее основе вывести уравнение перехода состояния

После того как мы принимаем решение по предмету \(i\) , остается подзадача, связанная с первыми \(i-1\) предметами. Здесь возможны два случая.

- Не класть предмет \(i\) : вместимость рюкзака не меняется, и состояние переходит в \([i-1, c]\) .
- Положить предмет \(i\) : вместимость рюкзака уменьшается на \(wgt[i-1]\) , а стоимость увеличивается на \(val[i-1]\) , и состояние переходит в \([i-1, c-wgt[i-1]]\) .

Этот анализ и раскрывает оптимальную подструктуру задачи: максимальная стоимость \(dp[i, c]\) равна лучшему из двух вариантов - не брать предмет \(i\) или взять предмет \(i\). Отсюда получается уравнение перехода состояния:

\[ dp[i, c] = \max(dp[i-1, c], dp[i-1, c - wgt[i-1]] + val[i-1]) \]

Нужно учитывать, что если вес текущего предмета \(wgt[i - 1]\) превышает оставшуюся вместимость \(c\) , то предмет можно только не брать.

Шаг 3: определить граничные условия и порядок переходов

Когда предметов нет или вместимость рюкзака равна \(0\) , максимальная стоимость равна \(0\). То есть весь первый столбец \(dp[i, 0]\) и вся первая строка \(dp[0, c]\) заполняются нулями.

Текущее состояние \([i, c]\) зависит от состояния сверху \([i-1, c]\) и состояния слева сверху \([i-1, c-wgt[i-1]]\) , поэтому достаточно двумя вложенными циклами пройти по всей таблице \(dp\) в прямом порядке.

После этого анализа реализуем по порядку: полный перебор, поиск с мемоизацией и динамическое программирование.

### 1. Метод 1: полный перебор

Код поиска содержит следующие элементы.

- Параметры рекурсии: состояние \([i, c]\) .
- Возвращаемое значение: решение подзадачи \(dp[i, c]\) .
- Условие завершения: когда номер предмета выходит за границу, то есть \(i = 0\) , или оставшаяся вместимость равна \(0\) , рекурсия завершается и возвращается стоимость \(0\) .
- Обрезка: если вес текущего предмета превышает оставшуюся вместимость рюкзака, то можно только не класть этот предмет.

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
knapsack.py

    def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int:
        """Рюкзак 0-1: полный перебор"""
        # Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 or c == 0:
            return 0
        # Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i - 1] > c:
            return knapsack_dfs(wgt, val, i - 1, c)
        # Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        no = knapsack_dfs(wgt, val, i - 1, c)
        yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
        # Вернуть вариант с большей стоимостью из двух возможных
        return max(no, yes)

knapsack.cpp

    /* Рюкзак 0-1: полный перебор */
    int knapsackDFS(vector<int> &wgt, vector<int> &val, int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFS(wgt, val, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = knapsackDFS(wgt, val, i - 1, c);
        int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Вернуть вариант с большей стоимостью из двух возможных
        return max(no, yes);
    }

knapsack.java

    /* Рюкзак 0-1: полный перебор */
    int knapsackDFS(int[] wgt, int[] val, int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFS(wgt, val, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = knapsackDFS(wgt, val, i - 1, c);
        int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Вернуть вариант с большей стоимостью из двух возможных
        return Math.max(no, yes);
    }

knapsack.cs

    /* Рюкзак 0-1: полный перебор */
    int KnapsackDFS(int[] weight, int[] val, int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (weight[i - 1] > c) {
            return KnapsackDFS(weight, val, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = KnapsackDFS(weight, val, i - 1, c);
        int yes = KnapsackDFS(weight, val, i - 1, c - weight[i - 1]) + val[i - 1];
        // Вернуть вариант с большей стоимостью из двух возможных
        return Math.Max(no, yes);
    }

knapsack.go

    /* Рюкзак 0-1: полный перебор */
    func knapsackDFS(wgt, val []int, i, c int) int {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 || c == 0 {
            return 0
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i-1] > c {
            return knapsackDFS(wgt, val, i-1, c)
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        no := knapsackDFS(wgt, val, i-1, c)
        yes := knapsackDFS(wgt, val, i-1, c-wgt[i-1]) + val[i-1]
        // Вернуть вариант с большей стоимостью из двух возможных
        return int(math.Max(float64(no), float64(yes)))
    }

knapsack.swift

    /* Рюкзак 0-1: полный перебор */
    func knapsackDFS(wgt: [Int], val: [Int], i: Int, c: Int) -> Int {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 || c == 0 {
            return 0
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i - 1] > c {
            return knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c)
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        let no = knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c)
        let yes = knapsackDFS(wgt: wgt, val: val, i: i - 1, c: c - wgt[i - 1]) + val[i - 1]
        // Вернуть вариант с большей стоимостью из двух возможных
        return max(no, yes)
    }

knapsack.js

    /* Рюкзак 0-1: полный перебор */
    function knapsackDFS(wgt, val, i, c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i === 0 || c === 0) {
            return 0;
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFS(wgt, val, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        const no = knapsackDFS(wgt, val, i - 1, c);
        const yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Вернуть вариант с большей стоимостью из двух возможных
        return Math.max(no, yes);
    }

knapsack.ts

    /* Рюкзак 0-1: полный перебор */
    function knapsackDFS(
        wgt: Array<number>,
        val: Array<number>,
        i: number,
        c: number
    ): number {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i === 0 || c === 0) {
            return 0;
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFS(wgt, val, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        const no = knapsackDFS(wgt, val, i - 1, c);
        const yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Вернуть вариант с большей стоимостью из двух возможных
        return Math.max(no, yes);
    }

knapsack.dart

    /* Рюкзак 0-1: полный перебор */
    int knapsackDFS(List<int> wgt, List<int> val, int i, int c) {
      // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
      if (i == 0 || c == 0) {
        return 0;
      }
      // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
      if (wgt[i - 1] > c) {
        return knapsackDFS(wgt, val, i - 1, c);
      }
      // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
      int no = knapsackDFS(wgt, val, i - 1, c);
      int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
      // Вернуть вариант с большей стоимостью из двух возможных
      return max(no, yes);
    }

knapsack.rs

    /* Рюкзак 0-1: полный перебор */
    fn knapsack_dfs(wgt: &[i32], val: &[i32], i: usize, c: usize) -> i32 {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 || c == 0 {
            return 0;
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i - 1] > c as i32 {
            return knapsack_dfs(wgt, val, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        let no = knapsack_dfs(wgt, val, i - 1, c);
        let yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1] as usize) + val[i - 1];
        // Вернуть вариант с большей стоимостью из двух возможных
        std::cmp::max(no, yes)
    }

knapsack.c

    /* Рюкзак 0-1: полный перебор */
    int knapsackDFS(int wgt[], int val[], int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFS(wgt, val, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = knapsackDFS(wgt, val, i - 1, c);
        int yes = knapsackDFS(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Вернуть вариант с большей стоимостью из двух возможных
        return myMax(no, yes);
    }

knapsack.kt

    /* Рюкзак 0-1: полный перебор */
    fun knapsackDFS(
        wgt: IntArray,
        _val: IntArray,
        i: Int,
        c: Int
    ): Int {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFS(wgt, _val, i - 1, c)
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        val no = knapsackDFS(wgt, _val, i - 1, c)
        val yes = knapsackDFS(wgt, _val, i - 1, c - wgt[i - 1]) + _val[i - 1]
        // Вернуть вариант с большей стоимостью из двух возможных
        return max(no, yes)
    }

knapsack.rb

    ### Рюкзак 0-1: полный перебор ###
    def knapsack_dfs(wgt, val, i, c)
      # Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
      return 0 if i == 0 || c == 0
      # Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
      return knapsack_dfs(wgt, val, i - 1, c) if wgt[i - 1] > c
      # Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
      no = knapsack_dfs(wgt, val, i - 1, c)
      yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
      # Вернуть вариант с большей стоимостью из двух возможных
      [no, yes].max
    end

Визуализация кода

Во весь экран >

Как показано на рисунке 14-18, поскольку каждый предмет создает две ветви поиска - «не брать» и «брать», временная сложность равна \(O(2^n)\) .

Посмотрев на дерево рекурсии, легко заметить наличие перекрывающихся подзадач, например \(dp[1, 10]\) и подобных. Когда число предметов растет, вместимость рюкзака велика, а особенно когда много предметов с одинаковым весом, количество перекрывающихся подзадач быстро увеличивается.

Рисунок 14-18 Дерево полного перебора для задачи о рюкзаке 0-1

### 2. Метод 2: мемоизация

Чтобы каждая перекрывающаяся подзадача вычислялась только один раз, используем таблицу памяти `mem` для хранения решений подзадач, где `mem[i][c]` соответствует \(dp[i, c]\) .

После введения мемоизации временная сложность определяется числом подзадач , то есть равна \(O(n \times cap)\) . Код выглядит так:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
knapsack.py

    def knapsack_dfs_mem(
        wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int
    ) -> int:
        """Рюкзак 0-1: поиск с мемоизацией"""
        # Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 or c == 0:
            return 0
        # Если запись уже есть, вернуть сразу
        if mem[i][c] != -1:
            return mem[i][c]
        # Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i - 1] > c:
            return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
        # Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
        yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
        # Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = max(no, yes)
        return mem[i][c]

knapsack.cpp

    /* Рюкзак 0-1: поиск с мемоизацией */
    int knapsackDFSMem(vector<int> &wgt, vector<int> &val, vector<vector<int>> &mem, int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если запись уже есть, вернуть сразу
        if (mem[i][c] != -1) {
            return mem[i][c];
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFSMem(wgt, val, mem, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
        int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = max(no, yes);
        return mem[i][c];
    }

knapsack.java

    /* Рюкзак 0-1: поиск с мемоизацией */
    int knapsackDFSMem(int[] wgt, int[] val, int[][] mem, int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если запись уже есть, вернуть сразу
        if (mem[i][c] != -1) {
            return mem[i][c];
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFSMem(wgt, val, mem, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
        int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = Math.max(no, yes);
        return mem[i][c];
    }

knapsack.cs

    /* Рюкзак 0-1: поиск с мемоизацией */
    int KnapsackDFSMem(int[] weight, int[] val, int[][] mem, int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если запись уже есть, вернуть сразу
        if (mem[i][c] != -1) {
            return mem[i][c];
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (weight[i - 1] > c) {
            return KnapsackDFSMem(weight, val, mem, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = KnapsackDFSMem(weight, val, mem, i - 1, c);
        int yes = KnapsackDFSMem(weight, val, mem, i - 1, c - weight[i - 1]) + val[i - 1];
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = Math.Max(no, yes);
        return mem[i][c];
    }

knapsack.go

    /* Рюкзак 0-1: поиск с мемоизацией */
    func knapsackDFSMem(wgt, val []int, mem [][]int, i, c int) int {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 || c == 0 {
            return 0
        }
        // Если запись уже есть, вернуть сразу
        if mem[i][c] != -1 {
            return mem[i][c]
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i-1] > c {
            return knapsackDFSMem(wgt, val, mem, i-1, c)
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        no := knapsackDFSMem(wgt, val, mem, i-1, c)
        yes := knapsackDFSMem(wgt, val, mem, i-1, c-wgt[i-1]) + val[i-1]
        // Вернуть вариант с большей стоимостью из двух возможных
        mem[i][c] = int(math.Max(float64(no), float64(yes)))
        return mem[i][c]
    }

knapsack.swift

    /* Рюкзак 0-1: поиск с мемоизацией */
    func knapsackDFSMem(wgt: [Int], val: [Int], mem: inout [[Int]], i: Int, c: Int) -> Int {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 || c == 0 {
            return 0
        }
        // Если запись уже есть, вернуть сразу
        if mem[i][c] != -1 {
            return mem[i][c]
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i - 1] > c {
            return knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c)
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        let no = knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c)
        let yes = knapsackDFSMem(wgt: wgt, val: val, mem: &mem, i: i - 1, c: c - wgt[i - 1]) + val[i - 1]
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = max(no, yes)
        return mem[i][c]
    }

knapsack.js

    /* Рюкзак 0-1: поиск с мемоизацией */
    function knapsackDFSMem(wgt, val, mem, i, c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i === 0 || c === 0) {
            return 0;
        }
        // Если запись уже есть, вернуть сразу
        if (mem[i][c] !== -1) {
            return mem[i][c];
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFSMem(wgt, val, mem, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        const no = knapsackDFSMem(wgt, val, mem, i - 1, c);
        const yes =
            knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = Math.max(no, yes);
        return mem[i][c];
    }

knapsack.ts

    /* Рюкзак 0-1: поиск с мемоизацией */
    function knapsackDFSMem(
        wgt: Array<number>,
        val: Array<number>,
        mem: Array<Array<number>>,
        i: number,
        c: number
    ): number {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i === 0 || c === 0) {
            return 0;
        }
        // Если запись уже есть, вернуть сразу
        if (mem[i][c] !== -1) {
            return mem[i][c];
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFSMem(wgt, val, mem, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        const no = knapsackDFSMem(wgt, val, mem, i - 1, c);
        const yes =
            knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = Math.max(no, yes);
        return mem[i][c];
    }

knapsack.dart

    /* Рюкзак 0-1: поиск с мемоизацией */
    int knapsackDFSMem(
      List<int> wgt,
      List<int> val,
      List<List<int>> mem,
      int i,
      int c,
    ) {
      // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
      if (i == 0 || c == 0) {
        return 0;
      }
      // Если запись уже есть, вернуть сразу
      if (mem[i][c] != -1) {
        return mem[i][c];
      }
      // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
      if (wgt[i - 1] > c) {
        return knapsackDFSMem(wgt, val, mem, i - 1, c);
      }
      // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
      int no = knapsackDFSMem(wgt, val, mem, i - 1, c);
      int yes = knapsackDFSMem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
      // Сохранить и вернуть вариант с большей стоимостью из двух решений
      mem[i][c] = max(no, yes);
      return mem[i][c];
    }

knapsack.rs

    /* Рюкзак 0-1: поиск с мемоизацией */
    fn knapsack_dfs_mem(wgt: &[i32], val: &[i32], mem: &mut Vec<Vec<i32>>, i: usize, c: usize) -> i32 {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if i == 0 || c == 0 {
            return 0;
        }
        // Если запись уже есть, вернуть сразу
        if mem[i][c] != -1 {
            return mem[i][c];
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if wgt[i - 1] > c as i32 {
            return knapsack_dfs_mem(wgt, val, mem, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        let no = knapsack_dfs_mem(wgt, val, mem, i - 1, c);
        let yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1] as usize) + val[i - 1];
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = std::cmp::max(no, yes);
        mem[i][c]
    }

knapsack.c

    /* Рюкзак 0-1: поиск с мемоизацией */
    int knapsackDFSMem(int wgt[], int val[], int memCols, int **mem, int i, int c) {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0;
        }
        // Если запись уже есть, вернуть сразу
        if (mem[i][c] != -1) {
            return mem[i][c];
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFSMem(wgt, val, memCols, mem, i - 1, c);
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        int no = knapsackDFSMem(wgt, val, memCols, mem, i - 1, c);
        int yes = knapsackDFSMem(wgt, val, memCols, mem, i - 1, c - wgt[i - 1]) + val[i - 1];
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = myMax(no, yes);
        return mem[i][c];
    }

knapsack.kt

    /* Рюкзак 0-1: поиск с мемоизацией */
    fun knapsackDFSMem(
        wgt: IntArray,
        _val: IntArray,
        mem: Array<IntArray>,
        i: Int,
        c: Int
    ): Int {
        // Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
        if (i == 0 || c == 0) {
            return 0
        }
        // Если запись уже есть, вернуть сразу
        if (mem[i][c] != -1) {
            return mem[i][c]
        }
        // Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
        if (wgt[i - 1] > c) {
            return knapsackDFSMem(wgt, _val, mem, i - 1, c)
        }
        // Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
        val no = knapsackDFSMem(wgt, _val, mem, i - 1, c)
        val yes = knapsackDFSMem(wgt, _val, mem, i - 1, c - wgt[i - 1]) + _val[i - 1]
        // Сохранить и вернуть вариант с большей стоимостью из двух решений
        mem[i][c] = max(no, yes)
        return mem[i][c]
    }

knapsack.rb

    ### Рюкзак 0-1: поиск с мемоизацией ###
    def knapsack_dfs_mem(wgt, val, mem, i, c)
      # Если все предметы уже рассмотрены или в рюкзаке не осталось места, вернуть стоимость 0
      return 0 if i == 0 || c == 0
      # Если запись уже есть, вернуть сразу
      return mem[i][c] if mem[i][c] != -1
      # Если вместимость рюкзака превышена, можно только не класть предмет в рюкзак
      return knapsack_dfs_mem(wgt, val, mem, i - 1, c) if wgt[i - 1] > c
      # Вычислить максимальную стоимость для случаев, когда предмет i не кладут и кладут
      no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
      yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
      # Сохранить и вернуть вариант с большей стоимостью из двух решений
      mem[i][c] = [no, yes].max
    end

Визуализация кода

Во весь экран >

На рисунке 14-19 показаны ветви поиска, которые были отсечены благодаря мемоизации.

Рисунок 14-19 Дерево поиска с мемоизацией для задачи о рюкзаке 0-1

### 3. Метод 3: динамическое программирование

По своей сути динамическое программирование здесь - это процесс последовательного заполнения таблицы \(dp\) в соответствии с переходами состояний. Код приведен ниже:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
knapsack.py

    def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
        """Рюкзак 0-1: динамическое программирование"""
        n = len(wgt)
        # Инициализация таблицы dp
        dp = [[0] * (cap + 1) for _ in range(n + 1)]
        # Переход состояний
        for i in range(1, n + 1):
            for c in range(1, cap + 1):
                if wgt[i - 1] > c:
                    # Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c]
                else:
                    # Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
        return dp[n][cap]

knapsack.cpp

    /* Рюкзак 0-1: динамическое программирование */
    int knapsackDP(vector<int> &wgt, vector<int> &val, int cap) {
        int n = wgt.size();
        // Инициализация таблицы dp
        vector<vector<int>> dp(n + 1, vector<int>(cap + 1, 0));
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[n][cap];
    }

knapsack.java

    /* Рюкзак 0-1: динамическое программирование */
    int knapsackDP(int[] wgt, int[] val, int cap) {
        int n = wgt.length;
        // Инициализация таблицы dp
        int[][] dp = new int[n + 1][cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[n][cap];
    }

knapsack.cs

    /* Рюкзак 0-1: динамическое программирование */
    int KnapsackDP(int[] weight, int[] val, int cap) {
        int n = weight.Length;
        // Инициализация таблицы dp
        int[,] dp = new int[n + 1, cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (weight[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i, c] = dp[i - 1, c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i, c] = Math.Max(dp[i - 1, c - weight[i - 1]] + val[i - 1], dp[i - 1, c]);
                }
            }
        }
        return dp[n, cap];
    }

knapsack.go

    /* Рюкзак 0-1: динамическое программирование */
    func knapsackDP(wgt, val []int, cap int) int {
        n := len(wgt)
        // Инициализация таблицы dp
        dp := make([][]int, n+1)
        for i := 0; i <= n; i++ {
            dp[i] = make([]int, cap+1)
        }
        // Переход состояний
        for i := 1; i <= n; i++ {
            for c := 1; c <= cap; c++ {
                if wgt[i-1] > c {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i-1][c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = int(math.Max(float64(dp[i-1][c]), float64(dp[i-1][c-wgt[i-1]]+val[i-1])))
                }
            }
        }
        return dp[n][cap]
    }

knapsack.swift

    /* Рюкзак 0-1: динамическое программирование */
    func knapsackDP(wgt: [Int], val: [Int], cap: Int) -> Int {
        let n = wgt.count
        // Инициализация таблицы dp
        var dp = Array(repeating: Array(repeating: 0, count: cap + 1), count: n + 1)
        // Переход состояний
        for i in 1 ... n {
            for c in 1 ... cap {
                if wgt[i - 1] > c {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
                }
            }
        }
        return dp[n][cap]
    }

knapsack.js

    /* Рюкзак 0-1: динамическое программирование */
    function knapsackDP(wgt, val, cap) {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array(n + 1)
            .fill(0)
            .map(() => Array(cap + 1).fill(0));
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = Math.max(
                        dp[i - 1][c],
                        dp[i - 1][c - wgt[i - 1]] + val[i - 1]
                    );
                }
            }
        }
        return dp[n][cap];
    }

knapsack.ts

    /* Рюкзак 0-1: динамическое программирование */
    function knapsackDP(
        wgt: Array<number>,
        val: Array<number>,
        cap: number
    ): number {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array.from({ length: n + 1 }, () =>
            Array.from({ length: cap + 1 }, () => 0)
        );
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            for (let c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = Math.max(
                        dp[i - 1][c],
                        dp[i - 1][c - wgt[i - 1]] + val[i - 1]
                    );
                }
            }
        }
        return dp[n][cap];
    }

knapsack.dart

    /* Рюкзак 0-1: динамическое программирование */
    int knapsackDP(List<int> wgt, List<int> val, int cap) {
      int n = wgt.length;
      // Инициализация таблицы dp
      List<List<int>> dp = List.generate(n + 1, (index) => List.filled(cap + 1, 0));
      // Переход состояний
      for (int i = 1; i <= n; i++) {
        for (int c = 1; c <= cap; c++) {
          if (wgt[i - 1] > c) {
            // Если вместимость рюкзака превышена, предмет i не выбирать
            dp[i][c] = dp[i - 1][c];
          } else {
            // Большее из двух решений: не брать или взять предмет i
            dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
          }
        }
      }
      return dp[n][cap];
    }

knapsack.rs

    /* Рюкзак 0-1: динамическое программирование */
    fn knapsack_dp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
        let n = wgt.len();
        // Инициализация таблицы dp
        let mut dp = vec![vec![0; cap + 1]; n + 1];
        // Переход состояний
        for i in 1..=n {
            for c in 1..=cap {
                if wgt[i - 1] > c as i32 {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = std::cmp::max(
                        dp[i - 1][c],
                        dp[i - 1][c - wgt[i - 1] as usize] + val[i - 1],
                    );
                }
            }
        }
        dp[n][cap]
    }

knapsack.c

    /* Рюкзак 0-1: динамическое программирование */
    int knapsackDP(int wgt[], int val[], int cap, int wgtSize) {
        int n = wgtSize;
        // Инициализация таблицы dp
        int **dp = malloc((n + 1) * sizeof(int *));
        for (int i = 0; i <= n; i++) {
            dp[i] = calloc(cap + 1, sizeof(int));
        }
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= cap; c++) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = myMax(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        int res = dp[n][cap];
        // Освободить память
        for (int i = 0; i <= n; i++) {
            free(dp[i]);
        }
        return res;
    }

knapsack.kt

    /* Рюкзак 0-1: динамическое программирование */
    fun knapsackDP(wgt: IntArray, _val: IntArray, cap: Int): Int {
        val n = wgt.size
        // Инициализация таблицы dp
        val dp = Array(n + 1) { IntArray(cap + 1) }
        // Переход состояний
        for (i in 1..n) {
            for (c in 1..cap) {
                if (wgt[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[i][c] = dp[i - 1][c]
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + _val[i - 1])
                }
            }
        }
        return dp[n][cap]
    }

knapsack.rb

    ### Рюкзак 0-1: динамическое программирование ###
    def knapsack_dp(wgt, val, cap)
      n = wgt.length
      # Инициализация таблицы dp
      dp = Array.new(n + 1) { Array.new(cap + 1, 0) }
      # Переход состояний
      for i in 1...(n + 1)
        for c in 1...(cap + 1)
          if wgt[i - 1] > c
            # Если вместимость рюкзака превышена, предмет i не выбирать
            dp[i][c] = dp[i - 1][c]
          else
            # Большее из двух решений: не брать или взять предмет i
            dp[i][c] = [dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1]].max
          end
        end
      end
      dp[n][cap]
    end

Визуализация кода

Во весь экран >

Как показано на рисунке 14-20, и временная сложность, и пространственная сложность определяются размером массива `dp` , то есть равны \(O(n \times cap)\) .

<1><2><3><4><5><6><7><8><9><10><11><12><13><14>

Рисунок 14-20 Процесс динамического программирования для задачи о рюкзаке 0-1

### 4. Оптимизация пространства

Поскольку каждое состояние зависит только от состояния в предыдущей строке, можно использовать два массива, которые будут продвигаться вперед по очереди, и тем самым уменьшить пространственную сложность с \(O(n \times cap)\) до \(O(cap)\) .

Если пойти дальше, можно спросить: можно ли оптимизировать память так, чтобы использовать только один массив? Наблюдение показывает, что каждое состояние зависит от клетки прямо сверху и клетки слева сверху. Предположим, что у нас есть только один массив, и в момент начала обхода строки \(i\) он еще хранит состояния строки \(i-1\) .

- Если обходить массив слева направо, то к моменту вычисления \(dp[i, j]\) значения слева сверху \(dp[i-1, 1]\) ~ \(dp[i-1, j-1]\) могут уже быть перезаписаны, и правильный результат перехода состояния получить не удастся.
- Если же обходить массив справа налево, проблема перезаписи не возникает, и переход состояния вычисляется корректно.

На рисунке 14-21 показан процесс перехода от строки \(i = 1\) к строке \(i = 2\) при использовании одного массива. С его помощью удобно понять различие между прямым и обратным обходом.

<1><2><3><4><5><6>

Рисунок 14-21 Процесс динамического программирования после оптимизации памяти для рюкзака 0-1

В коде для этого достаточно удалить первое измерение массива `dp` , а внутренний цикл заменить на обратный обход:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
knapsack.py

    def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
        """Рюкзак 0-1: динамическое программирование с оптимизацией памяти"""
        n = len(wgt)
        # Инициализация таблицы dp
        dp = [0] * (cap + 1)
        # Переход состояний
        for i in range(1, n + 1):
            # Обход в обратном порядке
            for c in range(cap, 0, -1):
                if wgt[i - 1] > c:
                    # Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c]
                else:
                    # Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
        return dp[cap]

knapsack.cpp

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    int knapsackDPComp(vector<int> &wgt, vector<int> &val, int cap) {
        int n = wgt.size();
        // Инициализация таблицы dp
        vector<int> dp(cap + 1, 0);
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            // Обход в обратном порядке
            for (int c = cap; c >= 1; c--) {
                if (wgt[i - 1] <= c) {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

knapsack.java

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    int knapsackDPComp(int[] wgt, int[] val, int cap) {
        int n = wgt.length;
        // Инициализация таблицы dp
        int[] dp = new int[cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            // Обход в обратном порядке
            for (int c = cap; c >= 1; c--) {
                if (wgt[i - 1] <= c) {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

knapsack.cs

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    int KnapsackDPComp(int[] weight, int[] val, int cap) {
        int n = weight.Length;
        // Инициализация таблицы dp
        int[] dp = new int[cap + 1];
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            // Обход в обратном порядке
            for (int c = cap; c > 0; c--) {
                if (weight[i - 1] > c) {
                    // Если вместимость рюкзака превышена, предмет i не выбирать
                    dp[c] = dp[c];
                } else {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.Max(dp[c], dp[c - weight[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

knapsack.go

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    func knapsackDPComp(wgt, val []int, cap int) int {
        n := len(wgt)
        // Инициализация таблицы dp
        dp := make([]int, cap+1)
        // Переход состояний
        for i := 1; i <= n; i++ {
            // Обход в обратном порядке
            for c := cap; c >= 1; c-- {
                if wgt[i-1] <= c {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = int(math.Max(float64(dp[c]), float64(dp[c-wgt[i-1]]+val[i-1])))
                }
            }
        }
        return dp[cap]
    }

knapsack.swift

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    func knapsackDPComp(wgt: [Int], val: [Int], cap: Int) -> Int {
        let n = wgt.count
        // Инициализация таблицы dp
        var dp = Array(repeating: 0, count: cap + 1)
        // Переход состояний
        for i in 1 ... n {
            // Обход в обратном порядке
            for c in (1 ... cap).reversed() {
                if wgt[i - 1] <= c {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
                }
            }
        }
        return dp[cap]
    }

knapsack.js

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    function knapsackDPComp(wgt, val, cap) {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array(cap + 1).fill(0);
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            // Обход в обратном порядке
            for (let c = cap; c >= 1; c--) {
                if (wgt[i - 1] <= c) {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

knapsack.ts

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    function knapsackDPComp(
        wgt: Array<number>,
        val: Array<number>,
        cap: number
    ): number {
        const n = wgt.length;
        // Инициализация таблицы dp
        const dp = Array(cap + 1).fill(0);
        // Переход состояний
        for (let i = 1; i <= n; i++) {
            // Обход в обратном порядке
            for (let c = cap; c >= 1; c--) {
                if (wgt[i - 1] <= c) {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        return dp[cap];
    }

knapsack.dart

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    int knapsackDPComp(List<int> wgt, List<int> val, int cap) {
      int n = wgt.length;
      // Инициализация таблицы dp
      List<int> dp = List.filled(cap + 1, 0);
      // Переход состояний
      for (int i = 1; i <= n; i++) {
        // Обход в обратном порядке
        for (int c = cap; c >= 1; c--) {
          if (wgt[i - 1] <= c) {
            // Большее из двух решений: не брать или взять предмет i
            dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
          }
        }
      }
      return dp[cap];
    }

knapsack.rs

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    fn knapsack_dp_comp(wgt: &[i32], val: &[i32], cap: usize) -> i32 {
        let n = wgt.len();
        // Инициализация таблицы dp
        let mut dp = vec![0; cap + 1];
        // Переход состояний
        for i in 1..=n {
            // Обход в обратном порядке
            for c in (1..=cap).rev() {
                if wgt[i - 1] <= c as i32 {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = std::cmp::max(dp[c], dp[c - wgt[i - 1] as usize] + val[i - 1]);
                }
            }
        }
        dp[cap]
    }

knapsack.c

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    int knapsackDPComp(int wgt[], int val[], int cap, int wgtSize) {
        int n = wgtSize;
        // Инициализация таблицы dp
        int *dp = calloc(cap + 1, sizeof(int));
        // Переход состояний
        for (int i = 1; i <= n; i++) {
            // Обход в обратном порядке
            for (int c = cap; c >= 1; c--) {
                if (wgt[i - 1] <= c) {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = myMax(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);
                }
            }
        }
        int res = dp[cap];
        // Освободить память
        free(dp);
        return res;
    }

knapsack.kt

    /* Рюкзак 0-1: динамическое программирование с оптимизацией памяти */
    fun knapsackDPComp(wgt: IntArray, _val: IntArray, cap: Int): Int {
        val n = wgt.size
        // Инициализация таблицы dp
        val dp = IntArray(cap + 1)
        // Переход состояний
        for (i in 1..n) {
            // Обход в обратном порядке
            for (c in cap downTo 1) {
                if (wgt[i - 1] <= c) {
                    // Большее из двух решений: не брать или взять предмет i
                    dp[c] = max(dp[c], dp[c - wgt[i - 1]] + _val[i - 1])
                }
            }
        }
        return dp[cap]
    }

knapsack.rb

    ### Рюкзак 0-1: динамическое программирование с оптимизацией памяти ###
    def knapsack_dp_comp(wgt, val, cap)
      n = wgt.length
      # Инициализация таблицы dp
      dp = Array.new(cap + 1, 0)
      # Переход состояний
      for i in 1...(n + 1)
        # Обход в обратном порядке
        for c in cap.downto(1)
          if wgt[i - 1] > c
            # Если вместимость рюкзака превышена, предмет i не выбирать
            dp[c] = dp[c]
          else
            # Большее из двух решений: не брать или взять предмет i
            dp[c] = [dp[c], dp[c - wgt[i - 1]] + val[i - 1]].max
          end
        end
      end
      dp[cap]
    end

Визуализация кода

Во весь экран >

##### Оставляйте свои идеи, вопросы и предложения в комментариях