Using dynamic programming to solve a version of the knapsack problem

Question

I'm working through MIT6.0002 on OpenCourseWare (https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0002-introduction-to-computational-thinking-and-data-science-fall-2016/assignments/) and I am stumped on Part B of Problem Set 1. The problem, which is presented as a version of the knapsack problem, is stated as follows:

[The Aucks have found a colony of geese that lay golden eggs of various weights] They want to carry as few eggs as possible on their trip as they don’t have a lot of space on their ships. They have taken detailed notes on the weights of all the eggs that geese can lay in a given flock and how much weight their ships can hold. Implement a dynamic programming algorithm to find the minimum number of eggs needed to make a given weight for a certain ship in dp_make_weight. The result should be an integer representing the minimum number of eggs from the given flock of geese needed to make the given weight. Your algorithm does not need to return what the weight of the eggs are, just the minimum number of eggs. Assumptions: -All the eggs weights are unique between different geese, but a given goose will always lay the same size egg - The Aucks can wait around for the geese to lay as many eggs as they need [ie there is an infinite supply of each size of egg]. -There are always eggs of size 1 available

The problem also states that the solution must use dynamic programming. I have written a solution (in Python) which I think finds the optimal solution, but it does not use dynamic programming, and I fail to understand how dynamic programming is applicable. It was also suggested that the solution should use recursion.

Can anybody explain to me what the advantage is of using memoization in this case, and what I would gain by implementing a recursive solution? (Apologies if my question is too vague or if the solution is too obvious for words; I'm a relative beginner to programming, and to this site).

My code:

#================================
# Part B: Golden Eggs
#================================

# Problem 1
def dp_make_weight(egg_weights, target_weight, memo = {}):
    """
    Find number of eggs to bring back, using the smallest number of eggs. Assumes there is
    an infinite supply of eggs of each weight, and there is always a egg of value 1.

    Parameters:
    egg_weights - tuple of integers, available egg weights sorted from smallest to largest value (1 = d1 < d2 < ... < dk)
    target_weight - int, amount of weight we want to find eggs to fit
    memo - dictionary, OPTIONAL parameter for memoization (you may not need to use this parameter depending on your implementation)

    Returns: int, smallest number of eggs needed to make target weight
    """
    egg_weights = sorted(egg_weights, reverse=True) 
    eggs = 0
    while target_weight != 0:
        while egg_weights[0] <= target_weight:
            target_weight -= egg_weights[0]
            eggs += 1
        del egg_weights[0]
    return eggs


# EXAMPLE TESTING CODE, feel free to add more if you'd like
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()

ggorlen ggorlen · Accepted Answer · 2020-05-06T22:25:01

The problem here is a classic DP situation where greediness can sometimes give optimal solutions, but sometimes not.

The situation in this problem is similar to the classic DP problem coin change where we wish to find the fewest number of different valued coins to make change given a target value. The denominations available in some countries such as the USA (which uses coins valued 1, 5, 10, 25, 50, 100) are such that it's optimal to greedily choose the largest coin until the value drops below it, then move on to the next coin. But with other denomination sets like 1, 3, 4, greedily choosing the largest value repeatedly can produce sub-optimal results.

Similarly, your solution works fine for certain egg weights but fails on others. If we choose our egg weights to be 1, 6, 9 and give a target weight of 14, the algorithm chooses 9 immediately and is then unable to make progress on 6. At that point, it slurps a bunch of 1s and ultimately thinks 6 is the minimal solution. But that's clearly wrong: if we intelligently ignore the 9 and pick two 6s first, then we can hit the desired weight with only 4 eggs.

This shows that we have to consider the fact that at any decision point, taking any of our denominations might ultimately lead us to a globally optimal solution. But we have no way of knowing in the moment. So, we try every denomination at every step. This is very conducive to recursion and could be written like this:

def dp_make_weight(egg_weights, target_weight):
    least_taken = float("inf")

    if target_weight == 0:
        return 0
    elif target_weight > 0:
        for weight in egg_weights:
            sub_result = dp_make_weight(egg_weights, target_weight - weight)
            least_taken = min(least_taken, sub_result)

    return least_taken + 1

if __name__ == "__main__":
    print(dp_make_weight((1, 6, 9), 14))

For each call, we have 3 possibilities:

Base case target_weight < 0: return something to indicate no solution possible (I used infinity for convenience).
Base case target_weight == 0: we found a candidate solution. Return 0 to indicate no step was taken here and give the caller a base value to increment.
Recursive case target_weight > 0: try taking every available egg_weight by subtracting it from the total and recursively exploring the path rooted at the new state. After exploring every possible outcome from the current state, pick the one that took the least number of steps to reach the target. Add 1 to count the current step's egg taken and return.

So far, we've seen that a greedy solution is incorrect and how to fix it but haven't motivated dynamic programming or memoization. DP and memoization are purely optimization concepts, so you can add them after you've found a correct solution and need to speed it up. Time complexity of the above solution is exponential: for every call, we have to spawn len(egg_weights) recursive calls.

There are many resources explaining DP and memoization and I'm sure your course covers it, but in brief, our recursive solution shown above re-computes the same results over and over by taking different recursive paths that ultimately lead to the same values being given for target_weight. If we keep a memo (dictionary) that stores the results of every call in memory, then whenever we re-encounter a call, we can look up its result instead of re-computing it from scratch.

def dp_make_weight(egg_weights, target_weight, memo={}):
    least_taken = float("inf")

    if target_weight == 0:
        return 0
    elif target_weight in memo:
        return memo[target_weight]
    elif target_weight > 0:
        for weight in egg_weights:
            sub_result = dp_make_weight(egg_weights, target_weight - weight)
            least_taken = min(least_taken, sub_result)

    memo[target_weight] = least_taken + 1
    return least_taken + 1

if __name__ == "__main__":
    print(dp_make_weight((1, 6, 9, 12, 13, 15), 724)) # => 49

Since we're using Python, the "Pythonic" way to do it is probably to decorate the function. In fact, there's a builtin memoizer called lru_cache, so going back to our original function without any memoization, we can add memoization (caching) with two lines of code:

from functools import lru_cache

@lru_cache
def dp_make_weight(egg_weights, target_weight):
    # ... same code as the top example ...

Memoizing with a decorator has the downside of increasing the size of the call stack proportional to the wrapper's size so it can increase the likelihood of blowing the stack. That's one motivation for writing DP algorithms iteratively, bottom-up (that is, start with the solution base cases and build up a table of these small solutions until you're able to build the global solution), which might be a good exercise for this problem if you're looking for another angle on it.

Using dynamic programming to solve a version of the knapsack problem

1 Answers