Overview

Given a list of product prices, this problem asks for the minimum number of products needed to select so that the total price is exactly S yen.

Analysis

This problem is a variant of the “subset sum problem,” where we need to find the minimum number of products among combinations that sum to S. If we try all combinations of selecting/not selecting each product, there would be \(2^N\) possibilities, and when N is up to 100, the computation becomes infeasible. Therefore, we need to solve this efficiently using dynamic programming.

Algorithm

We solve this using dynamic programming. Define the array dp[i] as “the minimum number of products needed to make the total price exactly i yen.” In the initial state, dp[0] = 0 (0 products needed to make 0 yen), and all other values are initialized to infinity (impossible).

For each product with price price, the minimum number of products to achieve a total of j yen is the smaller of: the minimum count for j-price yen plus 1 (if we select this product), or the current value of dp[j] (if we don’t select this product). By updating in descending order from S down to price, we prevent selecting the same product multiple times.

Complexity

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

Implementation Notes

• Initialize the array with infinity (INF) to represent unreachable states

• Iterate the total price loop in descending order (from S down to price) to prevent selecting the same product more than once

• At the end, if dp[S] is not INF, output its value; otherwise, output -1

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    S = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    INF = float('inf')
    dp = [INF] * (S + 1)
    dp[0] = 0
    
    for price in A:
        for j in range(S, price - 1, -1):
            if dp[j - price] != INF:
                dp[j] = min(dp[j], dp[j - price] + 1)
    
    print(dp[S] if dp[S] != INF else -1)

if __name__ == "__main__":
    main()

---

This editorial was generated by deepseekv3.