Knapsack 2 - Problem Statement

This is Knapsack 2 from AtCoder DP Contest: You have $n \le 100$ items. Each item has weight $w_i \le 10^9$ and value $v_i \le 1000$. Your bag holds weight $W \le 10^9$. Find the maximum value you can carry. The constraints are break the standard approach. $O(n \cdot W)$ is impossible when $W = 10^9$.

You need a different DP formulation. Flip the DP: try dp[value] = minimum weight to achieve exactly that value.