June_Joshua June_Joshua - 4 days ago 5
Python Question

Python Greedy Sum

I am currently working on this code and the only thing that seems to work is the "no solution." Also it seems that the code has an infinite loop and I can't seem to figure out how to solve it. If someone could point out my mistake it would be appreciated.

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]


Second method:

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

Here is something that works:

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"

I would offer more help on what is wrong with your code, but that is for the moment a moving target - you keep changing it!

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