divide and conquer and top down knapsack approach

mail@pastecode.io avatar
2 months ago
2.3 kB
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)

print(f' Max value obtained is {knapsackNoMemoization(3, [5, 100, 1000], [1, 3, 4], 5)}')

# 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 knapsackTopDownDP(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] + knapsackTopDownDP(n - 1, values, weights, W - weights[index], T)

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

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

Leave a Comment