0/1 Knapsack Problem with Dynamic Programming
If you are planning to call dp_make_weight for different egg weight lists, then the default memo argument should be handled as follows. Also, read my comments in the code:
def dp_make_weight(egg_weights, target_weight, memo=None):
    if memo is None:
        memo = {}

    infinity = float('inf')

    if target_weight < 0:
        return float('inf')
    elif target_weight == 0:
        return 0
    else: # target_weight must be > 0
        if target_weight in memo:
            return memo[target_weight]
        result = infinity
        for weight in egg_weights:
            # Only update result when dp_make_weight returns a value smaller than
            # the current result value. Also note that the current value of memo
            # is what is being passed and not a new, empty dict:
            new_result = dp_make_weight(egg_weights, target_weight - weight, memo)
            if new_result < result:
                result = new_result
        result += 1
        memo[target_weight] = result
        return result

if __name__ == '__main__':
    egg_weights = (1, 5, 10, 25)
    n = 99
    print("Egg weights =", egg_weights)
    print("n =", n)
    print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(egg_weights, n))

    print()

    egg_weights = (1, 6, 9, 12, 13, 15)
    n = 724
    print("Egg weights =", egg_weights)
    print("n =", n)
    print("Expected ouput: 49")
    print("Actual output:", dp_make_weight(egg_weights, n))

Prints:
Egg weights = (1, 5, 10, 25)
n = 99
Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)
Actual output: 9

Egg weights = (1, 6, 9, 12, 13, 15)
n = 724
Expected ouput: 49
Actual output: 49


This is my attempt at the problem asked in this thread. When I try to run it with input egg_weights = (1,5,10,25) and n = 99, it seems to run into an infinite loop. The code seems to give the correct answer for smaller n, albeit very slowly. What went wrong here?
def dp_make_weight(egg_weights, target_weight, memo = {}):
    if target_weight < 0:
        return float('inf')
    elif target_weight == 0:
        return 0
    elif target_weight > 0:
        try:
            return memo[target_weight]
        except:
            memo[target_weight] = float('inf')
            for weight in egg_weights:
                result = dp_make_weight(egg_weights, target_weight - weight, memo = {})
                if result < memo[target_weight]:
                    memo[target_weight] = result + 1
        return result + 1

Here's the code that was provided for testing purpose.
if __name__ == '__main__':
    egg_weights = (1, 5, 10, 25)
    n = 99
    print("Egg weights = (1, 5, 10, 25)")
    print("n = 99")
    print("Expected ouput: 9 (3 * 25 + 2 * 10 + 4 * 1 = 99)")
    print("Actual output:", dp_make_weight(egg_weights, n))
    print()

