Задача про рюкзак

Необхідні попередні знання: Вступ до динамічного програмування

Вступ

Розгляньмо такий приклад:

[USACO07 Dec] Charm Bracelet

Є $n$ різних предметів і рюкзак місткості $W$. Кожен предмет має 2 атрибути: вагу ($w_{i}$) і цінність ($v_{i}$). Потрібно вибрати підмножину предметів, які покласти в рюкзак так, щоб сумарна вага не перевищувала місткість $W$, а сумарна цінність була максимальною.

У наведеному вище прикладі кожен предмет має лише два можливі стани (взятий або не взятий), що відповідає двійковим 0 і 1. Тому цей тип задачі називають «задачею про рюкзак 0-1».

Коли підходить цей алгоритм?

• Чи потрібно вибрати підмножину предметів, що максимізує сумарну цінність за обмеженням на сумарну вагу (місткість $W$)?
• Чи вага $W$ (та ваги предметів) — цілі й достатньо малі, щоб таблиця розміру $O(nW)$ вмістилася в пам'ять і час?
• Чи кожен предмет береться щонайбільше один раз (0-1)? (якщо предмети повторюються необмежено — це варіант «необмеженого рюкзака» з прямим, а не зворотним порядком за $j$)

Рюкзак 0-1

Пояснення

У наведеному вище прикладі вхідними даними задачі є: вага $i$-го предмета $w_{i}$, цінність $i$-го предмета $v_{i}$ і загальна місткість рюкзака $W$.

Нехай $f_{i, j}$ — стан динамічного програмування, що зберігає максимальну сумарну цінність, яку може нести рюкзак місткості $j$, коли ми розглядаємо лише перші $i$ предметів.

Припускаючи, що всі стани для перших $i-1$ предметів вже опрацьовано, які варіанти ми маємо для $i$-го предмета?

• Коли його не кладемо в рюкзак, залишкова місткість не змінюється і сумарна цінність теж не змінюється. Тому максимальна цінність у цьому випадку дорівнює $f_{i-1, j}$
• Коли його кладемо в рюкзак, залишкова місткість зменшується на $w_{i}$, а сумарна цінність зростає на $v_{i}$, тож максимальна цінність у цьому випадку дорівнює $f_{i-1, j-w_i} + v_i$

Звідси ми можемо вивести рівняння переходу ДП:

$$f_{i, j} = \max(f_{i-1, j}, f_{i-1, j-w_i} + v_i)$$

Далі, оскільки $f_{i}$ залежить лише від $f_{i-1}$, ми можемо позбутися першого виміру. Отримуємо правило переходу

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

яке має виконуватися у порядку спадання $j$ (щоб $f_{j-w_i}$ неявно відповідало $f_{i-1,j-w_i}$, а не $f_{i,j-w_i}$).

Важливо зрозуміти це правило переходу, бо більшість переходів у задачах про рюкзак виводяться подібним чином.

Реалізація

Описаний алгоритм можна реалізувати за $O(nW)$ так:

C++

for (int i = 1; i <= n; i++)
  for (int j = W; j >= w[i]; j--)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

Python

for i in range(1, n + 1):
    # Йдемо у зворотному порядку, щоб кожен предмет узяти не більше одного разу
    for j in range(W, w[i] - 1, -1):
        f[j] = max(f[j], f[j - w[i]] + v[i])

TypeScript

for (let i = 1; i <= n; i++)
  // Йдемо у зворотному порядку, щоб кожен предмет узяти не більше одного разу
  for (let j = W; j >= w[i]; j--)
    f[j] = Math.max(f[j], f[j - w[i]] + v[i]);

Go

for i := 1; i <= n; i++ {
    // Йдемо у зворотному порядку, щоб кожен предмет узяти не більше одного разу
    for j := W; j >= w[i]; j-- {
        f[j] = max(f[j], f[j-w[i]]+v[i])
    }
}

Знову ж таки, зверніть увагу на порядок виконання. Його слід суворо дотримуватися, щоб забезпечити такий інваріант: безпосередньо перед опрацюванням пари $(i, j)$ значення $f_k$ відповідає $f_{i,k}$ для $k > j$, але $f_{i-1,k}$ для $k < j$. Це гарантує, що $f_{j-w_i}$ береться з $(i-1)$-го кроку, а не з $i$-го.

Повний рюкзак

Модель повного рюкзака схожа на рюкзак 0-1, єдина відмінність від рюкзака 0-1 полягає в тому, що предмет можна вибрати необмежену кількість разів, а не лише один раз.

Ми можемо скористатися ідеєю рюкзака 0-1, щоб означити стан: $f_{i, j}$ — максимальна цінність, яку може отримати рюкзак, використовуючи перші $i$ предметів за максимальної місткості $j$.

Слід зауважити, що хоча означення стану схоже на означення для рюкзака 0-1, його правило переходу відрізняється від правила для рюкзака 0-1.

Пояснення

Тривіальний підхід полягає в тому, щоб для перших $i$ предметів перебрати, скільки разів узяти кожен предмет. Часова складність цього — $O(n^2W)$.

Це дає таке рівняння переходу:

$$f_{i, j} = \max\limits_{k=0}^{\infty}(f_{i-1, j-k\cdot w_i} + k\cdot v_i)$$

Водночас воно спрощується до «плоского» рівняння:

$$f_{i, j} = \max(f_{i-1, j},f_{i, j-w_i} + v_i)$$

Причина, чому це працює, полягає в тому, що $f_{i, j-w_i}$ вже було оновлено через $f_{i, j-2\cdot w_i}$ і так далі.

Аналогічно до рюкзака 0-1, ми можемо позбутися першого виміру, щоб оптимізувати складність за пам'яттю. Це дає нам те саме правило переходу, що й для рюкзака 0-1.

$$f_j \gets \max(f_j, f_{j-w_i}+v_i)$$

Реалізація

Описаний алгоритм можна реалізувати за $O(nW)$ так:

C++

for (int i = 1; i <= n; i++)
  for (int j = w[i]; j <= W; j++)
    f[j] = max(f[j], f[j - w[i]] + v[i]);

Python

for i in range(1, n + 1):
    # Йдемо у прямому порядку, щоб дозволити брати предмет кілька разів
    for j in range(w[i], W + 1):
        f[j] = max(f[j], f[j - w[i]] + v[i])

TypeScript

for (let i = 1; i <= n; i++)
  // Йдемо у прямому порядку, щоб дозволити брати предмет кілька разів
  for (let j = w[i]; j <= W; j++)
    f[j] = Math.max(f[j], f[j - w[i]] + v[i]);

Go

for i := 1; i <= n; i++ {
    // Йдемо у прямому порядку, щоб дозволити брати предмет кілька разів
    for j := w[i]; j <= W; j++ {
        f[j] = max(f[j], f[j-w[i]]+v[i])
    }
}

Попри те, що правило переходу те саме, наведений вище код є неправильним для рюкзака 0-1.

Уважно придивившись до коду, ми бачимо, що для предмета $i$, який зараз опрацьовуємо, і поточного стану $f_{i,j}$, коли $j\geqslant w_{i}$, на $f_{i,j}$ впливатиме $f_{i,j-w_{i}}$. Це рівносильно можливості покласти предмет $i$ у рюкзак кілька разів, що відповідає задачі про повний рюкзак, а не задачі про рюкзак 0-1.

Кратний рюкзак

Кратний рюкзак — також варіант рюкзака 0-1. Головна відмінність у тому, що кожного предмета є $k_i$ штук, а не лише $1$.

Пояснення

Дуже проста ідея така: «вибрати кожен предмет $k_i$ разів» рівносильно тому, що «$k_i$ однакових предметів вибираються по одному». Таким чином ми зводимо це до моделі рюкзака 0-1, яку можна описати функцією переходу:

$$f_{i, j} = \max_{k=0}^{k_i}(f_{i-1,j-k\cdot w_i} + k\cdot v_i)$$

Часова складність цього процесу — $O(W\sum\limits_{i=1}^{n}k_i)$

Оптимізація бінарним групуванням

Ми так само розглядаємо зведення моделі кратного рюкзака до моделі рюкзака 0-1 для оптимізації. Часову складність $O(Wn)$ не можна оптимізувати далі описаним вище підходом, тож зосередимося на складовій $O(\sum k_i)$.

Нехай $A_{i, j}$ позначає $j$-й предмет, виділений із $i$-го предмета. У тривіальному підході, розглянутому вище, $A_{i, j}$ позначає той самий предмет для всіх $j \leq k_i$. Головна причина нашої низької ефективності в тому, що ми робимо багато повторюваної роботи. Наприклад, розгляньмо вибір $\{A_{i, 1},A_{i, 2}\}$ і вибір $\{A_{i, 2}, A_{i, 3}\}$. Ці дві ситуації цілком рівносильні. Тому оптимізація способу виділення значно зменшить часову складність.

Групування роблять ефективнішим, застосовуючи бінарне групування.

А саме, $A_{i, j}$ містить $2^j$ окремих предметів ($j\in[0,\lfloor \log_2(k_i+1)\rfloor-1]$). Якщо $k_i + 1$ не є цілим степенем $2$, то для компенсації використовують ще один набір розміру $k_i-(2^{\lfloor \log_2(k_i+1)\rfloor}-1)$.

За допомогою описаного способу виділення можна отримати будь-яку суму $\leq k_i$ предметів, вибравши кілька $A_{i, j}$. Після виділення кожного предмета описаним способом достатньо застосувати метод рюкзака 0-1, щоб розв'язати нове формулювання задачі.

Ця оптимізація дає нам часову складність $O(W\sum\limits_{i=1}^{n}\log k_i)$.

Реалізація

C++

index = 0;
for (int i = 1; i <= n; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

Python

items = []  # список згрупованих предметів (вага, цінність)
for i in range(n):
    p, h, k = read_item()  # вага, цінність, кількість штук
    c = 1
    while k > c:
        k -= c
        # Група з c копій предмета
        items.append((c * p, c * h))
        c *= 2
    # Залишковий набір розміру k
    items.append((p * k, h * k))

TypeScript

const items: [number, number][] = []; // список згрупованих предметів (вага, цінність)
for (let i = 0; i < n; i++) {
  let [p, h, k] = readItem(); // вага, цінність, кількість штук
  let c = 1;
  while (k > c) {
    k -= c;
    // Група з c копій предмета
    items.push([c * p, c * h]);
    c *= 2;
  }
  // Залишковий набір розміру k
  items.push([p * k, h * k]);
}

Go

type item struct{ w, v int } // вага, цінність
items := []item{}            // список згрупованих предметів
for i := 0; i < n; i++ {
    p, h, k := readItem() // вага, цінність, кількість штук
    c := 1
    for k > c {
        k -= c
        // Група з c копій предмета
        items = append(items, item{c * p, c * h})
        c *= 2
    }
    // Залишковий набір розміру k
    items = append(items, item{p * k, h * k})
}

Оптимізація монотонною чергою

У цій оптимізації ми прагнемо звести задачу про рюкзак до задачі про чергу з максимумом.

Для зручності опису покладемо $g_{x, y} = f_{i, x \cdot w_i + y} ,\space g'_{x, y} = f_{i-1, x \cdot w_i + y}$. Тоді правило переходу можна записати так:

$$g_{x, y} = \max_{k=0}^{k_i}(g'_{x-k, y} + v_i \cdot k)$$

Далі покладемо $G_{x, y} = g'_{x, y} - v_i \cdot x$. Тоді правило переходу можна виразити так:

$$g_{x, y} \gets \max_{k=0}^{k_i}(G_{x-k, y}) + v_i \cdot x$$

Це перетворюється на класичну форму оптимізації монотонною чергою. $G_{x, y}$ можна обчислити за $O(1)$, тож для фіксованого $y$ ми можемо обчислити $g_{x, y}$ за час $O(\lfloor \frac{W}{w_i} \rfloor)$. Отже, складність знаходження всіх $g_{x, y}$ дорівнює $O(\lfloor \frac{W}{w_i} \rfloor) \times O(w_i) = O(W)$. У такий спосіб загальна складність алгоритму зменшується до $O(nW)$.

Змішаний рюкзак

Задача про змішаний рюкзак поєднує три описані вище задачі. Тобто деякі предмети можна взяти лише раз, деякі — необмежено, а деякі — не більше ніж $k$ разів.

Задача може видаватися складною, але доки ви розумієте основні ідеї попередніх задач про рюкзак і поєднуєте їх разом, ви впораєтеся. Псевдокод розв'язку такий:

C++

for (each item) {
  if (0-1 knapsack)
    Apply 0-1 knapsack code;
  else if (complete knapsack)
    Apply complete knapsack code;
  else if (multiple knapsack)
    Apply multiple knapsack code;
}

Python

for item in items:
    if item.kind == "0-1":          # рюкзак 0-1
        apply_01_knapsack(item)
    elif item.kind == "complete":   # повний рюкзак
        apply_complete_knapsack(item)
    elif item.kind == "multiple":   # кратний рюкзак
        apply_multiple_knapsack(item)

TypeScript

for (const item of items) {
  if (item.kind === "0-1")          // рюкзак 0-1
    apply01Knapsack(item);
  else if (item.kind === "complete") // повний рюкзак
    applyCompleteKnapsack(item);
  else if (item.kind === "multiple") // кратний рюкзак
    applyMultipleKnapsack(item);
}

Go

for _, item := range items {
    switch item.kind {
    case "0-1": // рюкзак 0-1
        apply01Knapsack(item)
    case "complete": // повний рюкзак
        applyCompleteKnapsack(item)
    case "multiple": // кратний рюкзак
        applyMultipleKnapsack(item)
    }
}

Задачі для практики

• Atcoder: Knapsack-1
• Atcoder: Knapsack-2
• LeetCode - 494. Target Sum
• LeetCode - 416. Partition Equal Subset Sum
• CSES: Book Shop II
• DMOJ: Knapsack-3
• DMOJ: Knapsack-4

Відеоматеріали