medude's blog

By medude, history, 4 weeks ago, In English

Is there an efficient way to merge two knapsack DP tables which map max value to cost (or min cost to value)? The obvious solution would be to add each element from the second DP table into the first one at a time, but this would run O(W^2). Can we do better?

Tags dp
 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

If it's equivalent to adding

Unable to parse markup [type=CF_MATHJAX]

items into knapsack it can't be faster. But if you memorize which items were added into second knapsack DP, you can re-add them into first knapsack in

Unable to parse markup [type=CF_MATHJAX]

, which will be faster if

Unable to parse markup [type=CF_MATHJAX]

.