Python 贪心求和

Question

我目前正在处理这段代码，唯一似乎有效的是 "no solution." 另外，这段代码似乎有一个无限循环，我似乎无法弄清楚如何解决它.如果有人能指出我的错误，将不胜感激。

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

Python 贪心求和

Python Greedy Sum

python

algorithm

greedy