# non dp and top down dp for knapsack

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}')```