题解 | 点菜问题

def fun(price, value, n, c):
    dp = [0] * (c+1)
    for i in range(n):
        for j in range(c, price[i] - 1, -1):
            dp[j] = max(dp[j-price[i]] + value[i], dp[j])
    return dp[c]

while True:
    try:
        c, n = list(map(int, input().split()))
        price = []
        value = []
        for i in range(n):
            a, b = list(map(int, input().split()))
            price.append(a)
            value.append(b)
        res = fun(price, value, n, c)
        print(res)
    except:
        break