How does the zero-one knapsack pattern work?
LeetCode Patterns Flashcards: Dynamic Programming, Memoization, Tabulation, Patterns
Аудио-карточка · 0:30Nortren·
How does the zero-one knapsack pattern work?
0:30
Given items with weights and values, and a capacity limit, maximize total value without exceeding capacity. The state is the current item index and remaining capacity. For each item, choose to include it, adding its value and reducing capacity, or skip it, keeping the same capacity. The transition is: dp at index i with capacity c equals the maximum of dp at i plus one with c, which skips the item, or dp at i plus one with c minus weight of i plus value of i, which takes it. Build bottom-up filling a two-dimensional table.
neetcode.io