I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be misleading). Anyways, my question is this:
We are initially given a list of "items" to be filled in a knapsack of fixed size. Each item has a weight (bounded, integral) and value, and we need to maximize the total value of items in the knapsack. So far, this is identical to the 0/1 Knapsack problem. Now, at each step, we perform one of the following:
- Remove the first item in the list (first means encountered earliest)
- Add a new item to the list at the end.
To keep the solution space small, we can assume that the maximum size of the list is fixed, so that it will behave like a fixed size buffer overflow - oldest item is removed before new item is added.
Now, the list is smallish, so the initial instance of the knapsack on the original list can be performed to obtain the first solution. Now, after every operation on the list (addition or removal of items), we again want to find out the best way to fill a new (empty) knapsack with the items in the new list. And we want to do it without repeating a full knapsack algorithm on this slightly modified list (since there will be many such operations).
Is there some way the results of the previous state can be utilized to speed up the process? Is there some information from the previous state that can usually speed up the process? Is there any research on this or some related problem?
The pseudo-polynomial time DP algorithm can be adapted for the case where an item is added (since the table depends on the previous items), but I could not figure out how to deal with it in case the first item is removed from the list. Similarly, a branch-and-bound approach seems pointless. Any ideas or references?