Knapsack 2 - Implementation

V_max = sum of all values
dp[0] = 0, dp[v] = infinity for v > 0

for i from 1 to n:
    for v from V_max down to value[i]:
        dp[v] = min(dp[v], dp[v - value[i]] + weight[i])

answer = largest v where dp[v] <= W

Time: $O(n \cdot V_{max})$. With $n = 100$ and $V_{max} = 100{,}000$, that's $10^7$ operations.

Space: $O(V_{max})$ using 1D array.