输入的第一行有两个整数C(1 <= C <= 1000)和N(1 <= N <= 100),C代表总共能够报销的额度,N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间(包括1和100)的的整数,分别表示菜的>价格和菜的评价分数。
输出只包括一行,这一行只包含一个整数,表示在报销额度范围内,所点的菜得到的最大评价分数。
90 4 20 25 30 20 40 50 10 18 40 2 25 30 10 8
95 38
'''0-1背包问题''' def best(c, p, v, n): dp = [0]*(c+1) dp[0] = 0 for i in range(0, n): for j in range(c, p[i]-1, -1): dp[j] = max(dp[j], dp[j-p[i]] + v[i]) print(dp[c]) while True: try: price = [] vi = [] c, n = map(int, input().split()) for i in range(n): p, v = map(int, input().split()) price.append(p) vi.append(v) best(c, price, vi, n) except: break