Skip to content

Commit 36544e2

Browse files
Update src/dynamic_programming/knapsack.md
Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
1 parent 0df0b91 commit 36544e2

1 file changed

Lines changed: 1 addition & 1 deletion

File tree

src/dynamic_programming/knapsack.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ In the example above, the input to the problem is the following: the weight of $
2424

2525
Let $f_{i, j}$ be the dynamic programming state holding the maximum total value the knapsack can carry with capacity $j$, when only the first $i$ items are considered.
2626

27-
Consider the state transfer. Assuming that all states of first $i-1$ items have been processed, for the $i^{th}$ item;
27+
Assuming that all states of the first $i-1$ items have been processed, what are the options for the $i^{th}$ item?
2828
- When it is not put into the knapsack, the remaining capacity remains unchanged and total value does not change. Therefore, the maximum value in this case is $f_{i-1, j}$
2929
- When it is put into the knapsack, the remaining capacity decreases by $w_{i}$ and the total value increases by $v_{i}$,
3030
so the maximum value in this case is $f_{i-1, j-w_i} + v_i$

0 commit comments

Comments
 (0)