Dynamic programming script for the best way to sum numbers

Question

I'm trying to learn some basic stuff in dynamic programming, but I got stuck in the following problem:

given as input an integer sum and a list of positive integers numbers, return the list made of the smallest amount of number belonging to numbers that sum up to sum.

Hope this is clear, I'll give you three examples:

if sum = 10 and numbers = (2, 3, 5) should return [5, 5]; if sum = 0 and numbers = (2, 3, 5) should return []; if sum = 10 and numbers = (3) should return False.

def bestsum(sum, numbers, memo={}):
    if sum == 0:
        return []
    elif sum < 0:
        return False
    else:
        if sum not in memo:
            shortest_combination = False
            for number in numbers:
                remainder = sum - number
                combination = bestsum(remainder, numbers)
                if combination != False:
                    combination.append(number)
                    if shortest_combination == False or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[sum] = shortest_combination
        return memo[sum]

I do not put memo as an input of my recursive call of bestsum, since it worked with other dynamical programs I did before. Even if I add it, however, the script doesn't work, it update the memo even when I do not do that explicitly. Adding a copy.copy or actually inserting my memo as input doesn't help. Maybe the problem is that I still miss how variables live in my memory when I call different and maybe recursively other functions.

Two quick points. First, don't know variables keywords. That means you should rename your sum variable. Second, the function seems to either return a list or a bool. I would tighten that up. — bdempe, Dec 27 '20 at 18:37
Possible dup of [“Least Astonishment” and the Mutable Default Argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument). — martineau, Dec 27 '20 at 18:41
Does this answer your question? ["Least Astonishment" and the Mutable Default Argument](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) — Tomerikoo, Dec 27 '20 at 18:47

Turtlean · Answer 1 · 2020-12-27T19:33:43.470

I made some changes to the codebase and added some comments, but I kept most of them:

def bestsum(sum, numbers, memo={}):
    if sum == 0:
        return []
    elif sum < 0:
        return False
    else:
        if sum not in memo:
            for number in numbers:
                remainder = sum - number
                shortest_combination = bestsum(remainder, numbers, memo)
                if shortest_combination != False:
                    # Good news! We found a valid path from `sum` to the end
                    if (
                        sum not in memo
                        or len(memo[sum]) > len(shortest_combination) + 1
                    ):
                        # Either there's no entry in memo for `sum` yet
                        # Or we've found a better subpath than the current one
                        currently_best_combination = shortest_combination.copy()
                        currently_best_combination.insert(0, number)
                        memo[sum] = currently_best_combination
            if sum in memo:
                # Return value if we've found a valid path 
                return memo[sum]
            else:
                # Return false if not
                return False
        else:
            # If sum is already in `memo`, it's already the optimal way
            return memo[sum]

numbers = [2, 3, 5]
print(bestsum(10, numbers))
# [5, 5]

numbers = [2, 3, 5]
print(bestsum(0, numbers))
# []

numbers = [3]
print(bestsum(10, numbers))
# False

Cereal · Answer 2 · 2020-12-28T01:08:40.697

In addition to the problems laid out in the comments (namely mutable default argument, using the name of a builtin as a variable name) you would also run afoul of shallow copies if you were to pass on the memo argument (EDIT: actually come to think of it, that would happen regardless..).

The quickest fix for all of the problems mentioned with minimal changes would probably get you this

def bestsum(s, numbers, memo=None):
    if memo is None:
        memo = {}
    if s == 0:
        return []
    elif s < 0:
        return False
    else:
        if s not in memo:
            shortest_combination = False
            for number in numbers:
                remainder = s - number
                combination = bestsum(remainder, numbers, memo)
                if combination != False:
                    combination = combination.copy()
                    combination.append(number)
                    if shortest_combination == False or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[s] = shortest_combination
        return memo[s]

(this is not to say that this is the most elegant way of going about it, more of a direct fix for your code)

As for how I would do it:

def bestsum(s, numbers):
    sums = {0:[]}
    while(s not in sums and len(sums)>0):
        sums = {k+n:l+[n] for k,l in sums.items() for n in numbers if k+n<=s}
    if(s not in sums):
        return None
    else:
        return sums[s]

Dynamic programming script for the best way to sum numbers

2 Answers2