Skip to content

Instantly share code, notes, and snippets.

@syphh
Created February 28, 2022 14:02
Show Gist options
  • Save syphh/955b71b40aa47ea98c5362662dbf6099 to your computer and use it in GitHub Desktop.
Save syphh/955b71b40aa47ea98c5362662dbf6099 to your computer and use it in GitHub Desktop.
def knapsack(values, weights, k, i=0, lookup=None):
lookup = {} if lookup is None else lookup
if (i, k) in lookup:
return lookup[(i, k)]
if i == len(values):
return 0
elif k < 0:
return float('-inf')
else:
lookup[(i, k)] = max(values[i]+knapsack(values, weights, k-weights[i], i+1, lookup),
knapsack(values, weights, k, i+1))
return lookup[(i, k)]
@matheusfrancisco
Copy link

this code is not 100% correct it needs to check if weights[i] > k before adding

@matheusfrancisco
Copy link

matheusfrancisco commented Dec 16, 2023

def find_knapsack_top(v,w, k, i=0, lookup= None):
    lookup = {} if lookup is None else lookup
    if (i,k) in lookup:
        return lookup[(i,k)]

    if len(v) == i or k < 0:
        return 0
    elif (w[i] > k):
        return find_knapsack_top(v, w, k, i+1, lookup)
    else:
        lookup[(i,k)] = max(v[i]+ find_knapsack_top(v,w,k-w[i],i+1,lookup),
                            find_knapsack_top(v, w,k,i+1, lookup))
        return lookup[(i,k)]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment