蓝桥杯算法提高VIP-贪吃的大嘴

解题思路:

注意事项:

参考代码:

#总美味度,蛋糕种类数
m,n=map(int,input().split())
#记录每种蛋糕的美味度
vals=[]
#记录每种蛋糕的数量
nums=[]
for _ in range(n):
    val,num=map(int,input().split())
    vals.append(val)
    nums.append(num)
#dp[i]表示美味度i所需蛋糕数量的最少个数,初始定义为无穷大
dp=[float('inf')]*(m+1)
#dp[0]设置为0,否则永远都是inf
dp[0]=0
for i in range(n):
    for j in range(1,nums[i]+1):
        for k in range(m,vals[i]-1,-1):
            #美味度为k时可能是美味度为k-vals[i]的数量加上1个vals[i]的美味度构成
            #或者就是当前美味度为k的最少
            dp[k]=min(dp[k],dp[k-vals[i]]+1)
if dp[m]==float('inf'):
    print('><')
else:
    print(dp[m])