re:re:actable
Урок 044 минуты чтения

Как решать задачи 0 1 knapsack?

На этой странице
Кратко

0/1 Knapsack - классический DP-паттерн выбора предметов: каждый предмет можно взять или не взять. State обычно зависит от индекса предмета и оставшейся вместимости.

Вопрос

Как решать задачу 0/1 knapsack и как сократить память до одномерного массива?

Формулировка

Есть предметы:

weights[i], values[i]

Есть вместимость capacity.

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

Пример:

weights  = [1, 2, 3]
values   = [6, 10, 12]
capacity = 5

Жадный выбор по "ценности за килограмм" (6, 5, 4) возьмет предметы 1 и 2: вес 3, ценность 16. Третий уже не влезет. Но лучше взять предметы 2 и 3: вес 5, ценность 22. Поэтому нужен DP, который сравнивает варианты.

State

dp[i][w] = максимум ценности, используя первые i предметов и вместимость w

Transition

Не берем предмет:

dp[i][w] = dp[i - 1][w]

Берем предмет, если помещается:

dp[i][w] = dp[i - 1][w - weight] + value

Реализация

function knapsack(weights: number[], values: number[], capacity: number): number {
  const n = weights.length
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0))
 
  for (let i = 1; i <= n; i++) {
    const weight = weights[i - 1]
    const value = values[i - 1]
 
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w]
 
      if (weight <= w) {
        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weight] + value)
      }
    }
  }
 
  return dp[n][capacity]
}

Таблица для примера выше (строка - сколько первых предметов можно использовать, столбец - вместимость):

i \ w012345
0 предметов000000
+ предмет 1 (w1, v6)066666
+ предмет 2 (w2, v10)0610161616
+ предмет 3 (w3, v12)0610161822

Как получилось 22 в правом нижнем углу: не брать предмет 3 - это dp[2][5] = 16; взять - это 12 + dp[2][5 - 3] = 12 + 10 = 22. Выбираем максимум.

Time O(n * capacity), space O(n * capacity).

Как сократить память до одномерного массива

Строка i зависит только от строки i - 1, поэтому можно хранить одну строку и обновлять ее на месте:

function knapsack1D(weights: number[], values: number[], capacity: number): number {
  const dp = new Array(capacity + 1).fill(0)
 
  for (let i = 0; i < weights.length; i++) {
    // Идем от большей вместимости к меньшей!
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i])
    }
  }
 
  return dp[capacity]
}

Space становится O(capacity).

Почему цикл идет назад? dp[w - weight] должен быть значением из предыдущей строки, то есть без текущего предмета. При обходе справа налево ячейки левее еще не обновлены. Если идти слева направо, dp[w - weight] уже может включать текущий предмет, и он возьмется дважды:

предмет w1 v6, обход слева направо:
dp[1] = dp[0] + 6 = 6
dp[2] = dp[1] + 6 = 12   <- предмет взят дважды, это уже unbounded knapsack

Так что обход вперед - это решение другой задачи, где каждый предмет можно брать сколько угодно раз.

Что отвечать на собеседовании?

0/1 knapsack решается DP, где состояние зависит от номера предмета и оставшейся вместимости. На каждом шаге есть выбор: взять предмет или не взять. Каждый предмет можно взять только один раз, поэтому при переходе смотрим на предыдущую строку i - 1.

Что важно помнить: частые ошибки

  • Путать 0/1 knapsack и unbounded knapsack.
  • Неправильно идти по capacity при 1D optimization.
  • Забывать base row/column.
  • Использовать greedy по value/weight, хотя это не всегда корректно.
  • Ошибаться в индексах i - 1.

Мини-шпаргалка

  • Choice: take / skip.
  • State: i, capacity.
  • 2D DP: O(n * W).
  • 1D DP: O(W) памяти, вместимость идет от большей к меньшей.
  • Каждый предмет один раз.
  • Base: нули.
  • Greedy не гарантирует ответ.

Документация

Wikipedia: Knapsack problem.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам