Knapsack 2 - Transition

For each item $i$ and value $v$, you have two choices:

$1.$ Skip item $i$: $dp[i][v] = dp[i-1][v]$

$2.$

Take item $i$: $dp[i][v] = dp[i-1][v-v_i] + w_i$ (if $v \ge v_i$) Take the minimum: $dp[i][v] = \min(dp[i-1][v], dp[i-1][v-v_i] + w_i)$ After filling the table, scan from $V_{max}$ down to $0$. The first $v$ where $dp[n][v] \le W$ is your answer. This formula captures the relationship between smaller problems.