Knapsack 2 - State Design

Define $dp[i][v]$ as the minimum weight needed to achieve exactly value $v$ using items $1$ to $i$. Here $i$ ranges from $0$ to $n$, and $v$ ranges from $0$ to $V_{max}$ where $V_{max} = \sum v_i$.

Base cases:

$1.$ $dp[0][0] = 0$ (zero items, zero value, zero weight needed)

$2.$ $dp[0][v] = \infty$ for $v > 0$ (impossible to get positive value with no items)

The transition mirrors the original knapsack. For each item $i$, you either skip it and keep $dp[i-1][v]$, or include it and check $dp[i-1][v - v_i] + w_i$. You take the minimum of the two.