Overview

Given \(N\) products, select one or more items such that the total price is exactly \(S\) yen, and find the maximum total satisfaction. This is a variation of the classic 0-1 knapsack problem.

Analysis

Essence of the Problem

This problem asks us to maximize satisfaction under the constraint that the total price is exactly \(S\). In the standard knapsack problem, the constraint is that the total price is at most \(S\), but in this problem it must be exactly \(S\).

Naive Approach

Trying all possible selections of products gives \(2^N\) combinations. Since \(N\) can be up to \(3000\), \(2^{3000}\) is an astronomically large number, making brute force completely infeasible.

Solution Using Dynamic Programming (DP)

As with the knapsack problem, we use dynamic programming.

Define \(dp[j]\) as “the maximum satisfaction when selecting products such that the total price is exactly \(j\) yen.” If it is unachievable, set it to \(-1\).

The initial value is \(dp[0] = 0\) (selecting nothing gives a price of \(0\) yen and satisfaction of \(0\)), and all others are \(dp[j] = -1\).

Concrete example: \(N=3\), \(S=5\), products are \((V, C) = (3, 2), (4, 3), (1, 2)\)

• After processing product 1 \((V=3, C=2)\): \(dp[2] = 3\)
• After processing product 2 \((V=4, C=3)\): \(dp[2] = 3\), \(dp[3] = 4\), \(dp[5] = 7\)
• After processing product 3 \((V=1, C=2)\): \(dp[5] = \max(7, dp[3]+1) = \max(7, 5) = 7\)

The answer is \(dp[5] = 7\).

Algorithm

We use the 0-1 knapsack DP (1-dimensional array version).

1. Initialize \(dp[0] = 0\), \(dp[1] = dp[2] = \cdots = dp[S] = -1\).
2. For each product \((V_i, C_i)\), iterate in the order \(j = S, S-1, \ldots, C_i\) (reverse order) and do the following:
   • If \(dp[j - C_i] \geq 0\), update \(dp[j] = \max(dp[j],\ dp[j - C_i] + V_i)\).
3. The final answer is \(dp[S]\). If \(dp[S] = -1\), it is unachievable.

Reason for iterating in reverse order: This prevents the same product from being used more than once. If we iterate in ascending order, a value updated by a certain product could be further updated by the same product. By iterating in reverse, each product is used at most once.

Complexity

• Time complexity: \(O(N \times S)\) (for each product, we scan all amounts up to \(S\))
  • At most \(3000 \times 10000 = 3 \times 10^7\), which is sufficiently fast.
• Space complexity: \(O(S)\) (1-dimensional DP array)

Implementation Notes

• Initial value setup: Only \(dp[0] = 0\) is set as achievable; all others are \(-1\) (unachievable). This correctly handles the “exactly \(j\) yen” condition. In the standard knapsack problem (at most \(S\) yen), all values are initialized to \(0\), but in this problem, the distinction is necessary.

• Reverse loop: for j in range(S, c - 1, -1) guarantees that each product is selected at most once.

• Checking \(dp[j-c] \geq 0\): Before updating, verify that the source state is achievable. This prevents transitions from unachievable states (\(-1\)).

  Source Code

def main():
    N, S = map(int, input().split())
    items = []
    for _ in range(N):
        v, c = map(int, input().split())
        items.append((v, c))
    
    # dp[j] = maximum satisfaction when total cost is exactly j, -1 if not achievable
    dp = [-1] * (S + 1)
    dp[0] = 0
    
    for v, c in items:
        # Traverse in reverse to ensure each item is used at most once
        for j in range(S, c - 1, -1):
            if dp[j - c] >= 0:
                dp[j] = max(dp[j], dp[j - c] + v)
    
    print(dp[S])

main()

---

This editorial was generated by claude4.6opus-thinking.