Timeline for Dynamic programming knapsack solution
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 9, 2019 at 0:07 | comment | added | Saurabh | @GarethRees: Sorry I got the error because I didn't fully implement your review in the original post. | |
| Dec 8, 2019 at 10:42 | comment | added | Gareth Rees |
@Saurabh: Check your items argument: is it a list of pairs as required?
|
|
| Dec 8, 2019 at 3:53 | comment | added | Saurabh |
value, weight = items[i - 1] present above the return value of bestvalue function returns an error: ValueError: not enough values to unpack (expected 2, got 0)
|
|
| Oct 26, 2018 at 8:24 | history | edited | Gareth Rees | CC BY-SA 4.0 |
modernize code using lru_cache
|
| Jan 17, 2017 at 18:06 | comment | added | Gareth Rees |
@greendiod: I defined bestvalue inside knapsack because (i) it's only used there; (ii) it uses items from the outer scope (it would be a pain to have to pass this down through all the recursive calls); (iii) it's memoized so it has an associated cache that we don't want to keep around when knapsack has returned.
|
|
| Jan 17, 2017 at 13:43 | comment | added | green diod |
@GarethRees Do you need to define bestvalue() inside knapsack()? I would tend to avoid defining a function inside a function to make things clearer.
|
|
| Mar 13, 2014 at 8:26 | comment | added | Gareth Rees |
@Frank: yes, this solution uses len(items) levels of stack.
|
|
| Mar 8, 2014 at 15:13 | comment | added | Frank Smith | Beware of recursion depth limit issues with this proposed solution. | |
| Jan 16, 2013 at 22:19 | vote | accept | voithos | ||
| Jan 16, 2013 at 22:19 | comment | added | voithos | Thanks for your response (especially points 3 and 9)! I can't believe I forgot to consider the memoized recursive method. I'll apply some of your suggestions later today, hopefully. Thanks again. | |
| Jan 16, 2013 at 16:13 | history | edited | Gareth Rees | CC BY-SA 3.0 |
oops, 96
|
| Jan 16, 2013 at 15:47 | history | edited | Gareth Rees | CC BY-SA 3.0 |
show how to compute the solution from the top down with memoization
|
| Jan 16, 2013 at 15:41 | history | edited | Gareth Rees | CC BY-SA 3.0 |
show how to compute the solution from the top down with memoization
|
| Jan 16, 2013 at 12:20 | history | edited | Gareth Rees | CC BY-SA 3.0 |
added 24 characters in body
|
| Jan 16, 2013 at 12:15 | history | answered | Gareth Rees | CC BY-SA 3.0 |