Neomezený batoh

O(n·W)

Neomezený batoh je batoh 0/1 s jedním uvolněným pravidlem: každý typ předmětu lze použít, kolikrát chceš. Tabulka dp[i][w] stále drží nejlepší hodnotu pro kapacitu w s použitím typů 1..i, ale volba "vzít" teď čte stejný řádek — dp[i][w − váha] + hodnota — protože po vzetí předmětu ho můžeš vzít znovu. Tahle jediná změna (pohled na aktuální řádek místo na řádek nad) mění omezený problém na neomezený. Modeluje rozměňování s neomezenými mincemi, dělení materiálu i balení zdrojů. Jako jeho omezený příbuzný se vyplňuje v O(n·W).

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

Jak to funguje

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

Pseudokód

1unboundedKnapsack(weights, values, W):  # O(n·W)2  dp[0][w] ← 03  for each item i, capacity w in 1..W:4    best ← dp[i-1][w]                # skip this item type5    if w ≥ weight[i]:6      take ← dp[i][w-weight[i]] + value[i]   # reuse item i7      best ← max(best, take)8    dp[i][w] ← best9  return dp[n][W]