Knapsack 2 - Why Weight-Based DP Fails

Let's do the math. With $W = 10^9$, a DP table of size $n \times W$ would need $100 \times 10^9 = 10^{11}$ entries. That's $100$ billion operations and hundreds of gigabytes of memory. No amount of improvement saves you. The problem isn't implementation; it's the approach.

You need to change what you're computing. Look at the values instead: $v_i \le 1000$ and $n \le 100$. Maximum total value is at most $100{,}000$. That's a much smaller dimension.