Python Greedy Sum

Question

В настоящее время я работаю над этим кодом, и единственное, что работает, - это «нет решения». Также кажется, что код имеет бесконечный цикл, и я не могу понять, как его решить. Если кто-то может указать на мою ошибку, это будет оценено по достоинству.

def greedySum(L, s): 

""" input: s, positive integer, what the sum should add up to 
       L, list of unique positive integers sorted in descending order 
     Use the greedy approach where you find the largest multiplier for 
     the largest value in L then for the second largest, and so on to 
     solve the equation s = L[0]*m_0 + L[1]*m_1 + ... + L[n-1]*m_(n-1) 
     return: the sum of the multipliers or "no solution" if greedy approach does 
       not yield a set of multipliers such that the equation sums to 's' 
    """ 

     if len(L) == 0: 
      return "no solution"    
      sum_total = (0,()) 
     elif L[0] > k: 
      sum_total = greed(L[1:], k) 
     else: 
      no_number = L[0] 
      value_included, take = greed(L, k - L[0]) 
      value_included += 1 
      no_value, no_take = greed(L[1:], k) 
      if k >= 0: 
       sum_total = (value_included, take + (no_number,)) 
      else: 
       sum_total = (value_included, take + (no_number,)) 
     return sum_total 
    sum_multiplier = greed(L, s) 
    return "no solution" if sum(sum_multiplier[1]) != s else sum_multiplier[0] 

Второй метод:

def greedySum(L, s): 
     answer = [] 
    try: 
     while (s >= L[0]): 
     total = s// L[0] 
     s -= (total * L[0]) 
     answer.append(total) 
     L = L[1:] 
    return(str(answer)[1:-1]) 
    except: 
    return("no solution") 

Answer 1

Вот то, что работает:

def greedySum(L, s): 
    multiplier_sum = 0 
    for l in L: 
     (quot,rem) = divmod(s,l) # see how many 'l's you can fit in 's' 
     multiplier_sum += quot # add that number to the multiplier_sum 
     s = rem     # update the remaining amount 

    # If at the end and s is 0, return the multiplier_sum 
    # Otherwise, signal that there is no solution 
    return multiplier_sum if s == 0 else "no solution" 

я хотел бы предложить больше помощи на том, что случилось с вашим кодом, но это на момент движущаяся цель - вы меняете ее!

>>> greedySum([4,2],8) 
2 
>>> greedySum([4,2],9) 
'no solution' 
>>> greedySum([4,2,1],9) 
3