Problém batohu 0/1

O(n·W)

Pro dané předměty s váhami a hodnotami a celkovou váhovou kapacitou vybere problém batohu 0/1 podmnožinu s maximální hodnotou, která se ještě vejde — každý předmět se vezme celý, nebo se nechá (žádné zlomky). Tabulka dp[i][w] drží nejlepší hodnotu s použitím prvních i předmětů v rámci kapacity w. Každá buňka je lepší ze dvou možností: předmět i přeskočit (zkopírovat hodnotu z řádku nad) nebo ho vzít (jeho hodnota plus nejlepší pro zbývající kapacitu w − váha, z řádku nad). Vyplnění tabulky je O(n·W); buňka vpravo dole je optimum. Modeluje rozpočtování, nakládání nákladu i alokaci zdrojů a — jako součet podmnožiny — je NP-těžký, ale tady řešený pseudopolynomiálně.

DP tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Bez předmětů drží každá kapacita hodnotu 0 — základní řádek.
  2. Pro každý předmět a kapacitu nejprve zkopíruj nejlepší hodnotu, která tento předmět přeskočí (řádek nad).
  3. Pokud se předmět vejde, porovnej s jeho hodnotou plus nejlepší pro zbývající kapacitu.
  4. Ponech větší; buňka vpravo dole je nejhodnotnější náklad.

Pseudokód

1knapsack(weights, values, W):       # O(n·W)2  dp[0][w] ← 0                       # no items → no value3  for each item i, capacity w in 1..W:4    best ← dp[i-1][w]                # skip item i5    if w ≥ weight[i]:6      take ← dp[i-1][w-weight[i]] + value[i]7      best ← max(best, take)         # take item i8    dp[i][w] ← best9  return dp[n][W]