Overview

This is a classic knapsack problem where we select items within a budget of \(K\) yen to maximize the total amount spent.

Analysis

This problem is a variant of the “0-1 knapsack problem,” where each item can be selected at most once. A naive brute-force approach would require examining \(2^N\) possible selections, and when \(N\) is at most 100, \(2^{100}\) is astronomically large, making it impractical. Instead, we can efficiently find the solution using dynamic programming.

Algorithm

We solve this using dynamic programming. We initialize an array dp of size \(K+1\), where dp[j] records the maximum total amount achievable when we can spend up to \(j\) yen.

For each item, we loop in descending order from budget \(K\) yen down to the item’s price \(c\) yen. For each budget \(j\), we compare the case of not selecting the item (the current dp[j]) with the case of selecting it (dp[j - c] + c), and take the larger value. By processing in descending order, we prevent selecting the same item more than once.

Finally, the maximum value in the dp array is the maximum total amount achievable within the budget of \(K\) yen.

Complexity

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

Implementation Notes

• The array dp is initialized with zeros

• It is crucial that the inner loop processes in descending order (from \(K\) down to \(c\)) — if done in ascending order, the same item could be selected multiple times

• We obtain the final answer with max(dp) (since dp[K] is not necessarily the maximum value)

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    K = int(data[1])
    C = list(map(int, data[2:2+n]))
    
    dp = [0] * (K + 1)
    
    for c in C:
        for j in range(K, c - 1, -1):
            if dp[j] < dp[j - c] + c:
                dp[j] = dp[j - c] + c
                
    print(max(dp))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.