Overview

This is a problem where you select products such that the total price is exactly \(S\) yen, and you want to maximize the total satisfaction. If no such selection exists, output \(-1\).

Analysis

This problem is a variant of the “knapsack problem” where each product can be selected at most once. However, unlike the standard knapsack problem, the total price must be exactly \(S\) yen. A naive brute-force approach would require trying \(2^N\) combinations, which is impractical since \(N\) can be up to 3000.

This can be solved efficiently using dynamic programming. Define dp[j] as “the maximum total satisfaction among all ways to select products whose total price is exactly j yen.” If there is no way to achieve a total of exactly j yen, we manage this with a special value such as negative infinity.

Algorithm

1. Initialize dp[0] = 0 (exactly 0 yen corresponds to selecting nothing, with satisfaction 0), and initialize all other entries to negative infinity (\(\mathrm{INF}\)).
2. For each product with price \(c_i\) and satisfaction \(v_i\), loop from \(S\) down to \(c_i\) in reverse order.
3. If dp[j - c_i] is not \(\mathrm{INF}\) (i.e., there exists a way to achieve exactly j - c_i yen), check whether dp[j] can be updated with dp[j - c_i] + v_i.
4. After processing all products, if dp[S] is still \(\mathrm{INF}\), output -1; otherwise, output dp[S].

This method is known as the “exact” version of the 0-1 knapsack problem. By looping in reverse order, we ensure that the same product is not selected more than once.

Complexity

• Time complexity: \(O(N \cdot S)\)
• Space complexity: \(O(S)\)

Implementation Notes

• During initialization, set dp[0] = 0 and all other entries to a sufficiently small value (\(\mathrm{INF}\))

• Loop from larger amounts to smaller amounts (to prevent selecting the same product multiple times)

• If dp[S] remains at its initial value, output -1

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    S = int(data[1])
    V = []
    C = []
    index = 2
    for i in range(n):
        v = int(data[index])
        c = int(data[index+1])
        index += 2
        V.append(v)
        C.append(c)
    
    INF = -10**18
    dp = [INF] * (S+1)
    dp[0] = 0
    
    for i in range(n):
        c_i = C[i]
        v_i = V[i]
        for j in range(S, c_i-1, -1):
            if dp[j - c_i] != INF:
                if dp[j] < dp[j - c_i] + v_i:
                    dp[j] = dp[j - c_i] + v_i
    
    if dp[S] == INF:
        print(-1)
    else:
        print(dp[S])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.