Python array recursion, greatest possible sum

1618 views python
1

I have an array of 21 elements. I can either choose to NOT take an element, take it once, take it twice. I need to write a function that returns the greatest possible sum of elements that is <= 100. I am having trouble wrapping my head around the base cases of how do I stop properly when I'm over 100 already. I Know there are 2 conditions to stop. 1. The index is out of bounds. 2. The sum is over 100. But what do I return then??

def func(array, index, sum):
    # I need to stop here
    if index > 20:
        return sum # 
    #It's a candidate
    if sum <= 100:
        return sum
    # I need to stop here
    if sum > 100:
        return what?


    x = func(array, index + 1, sum)
    y = func(array, index + 1, sum + array[index])
    z = func(array, index + 1, sum + 2*array[index])

    return max([x,y,z])

print(func([22,64,1,4,7,9,4,7,56,23,67,12,89,34,12,16,42,54,32,12,54,23], 0, 0))

This should return 100 because I can put together 100 using these elements. For example 64 + 22 + 7 + 4 + 1 or w/e combination including 2x or not at all.

Can somebody explain what I should be returning in those base cases, should I have another variable?

answered question

1 Answer

10

If the sum is over 100, you need to reject that attempt and backtrack. You can return any value you want as long as it can be processed by the recursively calling code. I'd suggest a negative value, as that will always be less than some previously tried value (and so discarded by max).

Note that you should also change the order of your tests around. You need to test for an invalid sum before you test for going past the last index, as otherwise you could always go over 100 with the last number. Further, you don't want to return early if sum <= 100, as that's the recursive case.

def func(array, index, sum):
    if sum > 100:             # sum is too large, backtrack
        return -1

    if index >= len(array):   # we've reached the end of the input, return the sum
        return sum

    # you don't need an "if sum <= 100" test for a base case, that's the recursive case

    ...

posted this

Have an answer?

JD

Please login first before posting an answer.