Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

[Question] Merging Knapsacks

Правка en1, от 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?

Теги dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский andrewtam 2021-09-29 01:05:17 287 Initial revision (published)