Can someone help me with solving a problem of online knapsack with small constraints. Formally: you have a knapsack that can fit items of weight at most W. You are given N queries, where each query is one of:
Add a new item of weight w and cost s to a set of possible objects.
Remove the oldest item from the set of possible objects (the one which was added to the set before others)
Solve knapsack — print the largest cost you can achieve by choosing some objects from your current set so that their combined weight is at most W.
W <= 2000 (fixed and is given to you)
N <= 10000
Cost <= 1000000
There can be at most L = 2000 items in your set of objects at any time.
TL: 5 seconds
Example (W = 100):
There are a LOT of articles about online knapsack problem out there, but most of them try to approximate the result. In this case, we have a pretty small constraint on W, but I cannot take advantage of this. The naive approach (do a DP each time a knapsack query comes along) gets a TL.