python-贪吃的大嘴

解题思路:
一维费用背包问题（多重背包）
注意事项:

参考代码:

from cmath import inf  
  
def f(n,m):    
    dp = [inf for j in range(m+1)]  
    dp[0] = 0  
  
    V = [None]  
    W = [None]  
    for i in range(1,n+1):  
        v,num = map(int,input().strip().split())  
  
        k = 1  
        while num >= k:  
            num = num - k  
            W.append(k)  
            V.append(k*v)  
            k = k*2  
        if num > 0:  
            W.append(num)  
            V.append(num*v)  
    for i in range(1,len(W)):  
        for j in range(m,V[i]-1,-1):  
            dp[j] = min(dp[j],dp[j-V[i]]+W[i])  
  
    if dp[m] != inf:  
        print(dp[m])  
    else:  
        print('><')  
      
         
     
if __name__ == '__main__':    
    m,n = map(int,input().strip().split())  
    f(n,m)