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?
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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$$$.
I see, thanks!