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

[Question] Merging Knapsacks

Revision en1, by andrewtam, 2021-09-29 01:05:17

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English andrewtam 2021-09-29 01:05:17 287 Initial revision (published)