We can assume there are infinitely many dummy items with weights that are powers of \(2\) and value \(0\), so we only need to consider choosing items such that the sum of weights is exactly \(W\).

When \(W\) is even, the number of items with weight \(1\) that we choose must be even. In this case, it’s clearly optimal to choose them in descending order of value. In other words, we can pair up items with weight \(1\) in descending order of value, treating each pair as a single item with weight \(2\). By performing this operation, all weights become even, so we can divide both \(W\) and all item weights by \(2\) without changing the answer.

When \(W\) is odd, we need to choose an odd number of items with weight \(1\). In this case, we must choose the item with weight \(1\) that has the maximum value, and then we can reduce this to the case where \(W\) is even.

By repeating this procedure at most \(O(\log W)\) times, \(W\) becomes \(0\), and the total value of the chosen items at that point is the answer. With a proper implementation, the time complexity per test case is \(O(N \log N + \log W)\). (Code)