This problem is identical to Problem D - Knapsack 1 except the constraint that knapsack capacity \(W\) may be as large as \(10^9\). Thus, the previous solution that runs in \(O(NW)\) time is insufficient for this problem.

On the other hand, we can exploit the fact that the value \(v_i\) of each item is now at most \(10^3\). Let \(V=\sum_{i=1}^N v_i\) and, for \(1\leq i\leq N\) and \(0\leq j\leq V\), define \(f(i, j)\) as the minimum total weight of a subset of the first \(i\) items whose values sum to exactly \(j\). Moreover, define sentinel values \(f(0, 0)=0\) and \(f(0, j)=\infty\) for \(j\gt0\).

Following a similar argument to Problem D, but with the roles of weight and value swapped, the minimum total weight \(f(i, j)\) for \(i\geq1\) is either \(f(i-1, j)\) if Taro discards item \(i\) or \(f(i-1, j-\textcolor{red}{v_i})+\textcolor{red}{w_i}\) if Taro keeps item \(i\), so \(f(i, j)\) can be expressed as

\[ f(i, j)= \begin{cases} f(i-1, j)&\quad\text{if } j\lt \textcolor{red}{v_i},\\ \textcolor{red}{\min}(f(i-1,j),f(i-1, j-\textcolor{red}{v_i})+\textcolor{red}{w_i})&\quad\text{otherwise.} \end{cases} \]

Finally, the maximum possible sum of values is the greatest number \(j\) for which \(f(N, j)\leq W\).

As there are only \(NV\leq10^7\) possible combinations of \(i\) and \(j\), we can compute all values of \(f(i, j)\) in \(O(NV)\) time instead of \(O(NW)\) time. The implementation below reuses variables across iterations to store the dp array in \(O(V)\) space.

Sample code (Python):

N, W = (int(x) for x in input().split())
items = [[int(x) for x in input().split()] for _ in range(N)]

V = sum(v for _, v in items)
dp = [W + 1] * (V + 1)
dp[0] = 0
for w, v in items:
    for j in range(V, v - 1, -1):
        dp[j] = min(dp[j], dp[j - v] + w)

for j in range(V, -1, -1):
    if dp[j] <= W:
        print(j)
        break