Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

andrewtam's blog

[Question] Merging Knapsacks
By andrewtam, history, 3 years 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

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

If it's equivalent to adding $$$O(W)$$$ 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 $$$O(NW)$$$, which will be faster if $$$N < W$$$.

→ Reply