This variant of knapsack problem is known as the 0-1 knapsack problem because the knapsack can only contain zero or one copy of each kind of item.

Let \(f(i, j)\) be the maximum sum of values if Taro only chooses from the first \(i\) items and the capacity of the knapsack is \(j\). We define sentinel values \(f(0, j)=0\) for all \(j\in\{0, \dots, W\}\).

For \(1\leq i\leq N\) and \(0\leq j\leq W\), Taro can choose to either discard item \(i\) or keep item \(i\). If Taro discards item \(i\), his knapsack will only contain his choice among the first \(i-1\) items, so \(f(i,j)=f(i-1,j)\). If Taro keeps item \(i\), his choice among the first \(i-1\) items should only occupy a total weight of \(j-w_i\), so \(f(i,j)=f(i-1,j-w_i)+v_i\). Noting that the weight \(w_i\) may not exceed capacity \(j\), we can express \(f(i,j)\) as

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

Thus, we can iterate over \(N\) values of \(i\) and \(W+1\) values of \(j\) to obtain a solution that runs in \(O(NW)\) time.

Furthermore, since the sum of values remains unchanged whenever Taro discards an item, we can reuse variables between iterations and only update them if keeping an item results in a greater sum of values. This approach reduces space complexity from \(O(NW)\) to \(O(W)\).

In the implementation below, values of \(j\) are processed in descending order to ensure each item is added at most once. If they were processed in ascending order, an update \(\text{dp}[j+w_i]\leftarrow\text{dp}[j]+v_i\) would incorrectly propagate to \(\text{dp}[j+2w_i]\leftarrow\text{dp}[j+w_i]+v_i\) and so on. (Notably, the final result \(\text{dp}[W]\) would instead give the maximum sum of values if there were unlimited copies of each kind of item. This variant of knapsack problem is known as the unbounded knapsack problem.)

Sample code (Python):

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

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

print(dp[-1])