non dp and top down dp for knapsack

mail@pastecode.io avatar
unknown
python
2 months ago
2.8 kB
13
Indexable
Never
from typing import List


# the code to the knapsack problem with no memoization, only recursion
def knapsackNoMemoization(n, values: List, weights: List, W) -> int:
    # base case, if there's no items left or the weight constraint is now 0
    if n == 0 or W == 0:
        return 0
    
    # each refers to taking or leaving the last item (divide and conquer, remember?)
    take_it, leave_it = 0, 0
    
    # the last index is n - 1, we're using this to make the code a little more readable. at each step, we're 'peeling' away the last index.
    index = n - 1 
    
    # the 'take it' case - assuming it fits into the knapsack, do we include the item and decrement the weight or not?
    if weights[index] <= W:

        # the logic for this is if we take the item, we take it, and add it to the maximimum amount solved later in the sub problems
        take_it = values[index] + knapsackNoMemoization(n - 1, values, weights, W - weights[index])

    # otherwise, we leave it (so don't adjust weight)
    leave_it = knapsackNoMemoization(n - 1, values, weights, W)
    # then we constantly just try to take the max of both, basically asking ourselves, 'hey, is it more profitable to include it and look at the rest of the bag? or what if we don't include it because it doesn't fit and look at the rest of the bag?'
    return max(take_it, leave_it)


# The top down approach is EXACTLY THE SAME as the divide and conquer approach, but we have to now store the n x W subproblems as a 2D array.

def knapSackTopDown(n: int, values: List, weights: List, W: int) -> int:

    T = [[None] * (W + 1) for _ in range(n + 1)]

    def knapsackTopDownDPHelper(n: int, values: List, weights: List, W: int, T: List[List]) -> int:
        if n <= 0 or W <= 0:
            return 0
        
        # the reason we use n and W is they will be decremented over time with each recursive call
        # anyways, if the solution has been stored, just retrieve it
        if T[n][W] is not None:
            return T[n][W]
        
        take_it, leave_it = 0, 0

        index = n - 1

        if weights[index] <= weights:
            take_it = values[index] + knapsackTopDownDPHelper(n - 1, values, weights, W - weights[index], T)

        leave_it = knapsackTopDownDPHelper(n - 1, values, weights, W, T)

        T[n][W] = max(take_it, leave_it)
        return 
    

import time

start1 = time.time()
no_dp = knapsackNoMemoization(5, [300, 34, 20, 15, 100], [3, 10, 2, 1, 10], 10)
end1 = time.time()

start2 = time.time()
dp = knapSackTopDown(5, [300, 34, 20, 15, 100], [3, 10, 2, 1, 10], 10)
end2 = time.time()
    
print(f'no dp is {no_dp}, Time for no DP: {end1 - start1}. dp is {dp}, Time for DP: {end2 - start2}')
Leave a Comment