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?
abcdef
(in that order) to pick from; if you choose to picka
, at the next step do you get to pick frombcdefg
or fromcdefg
? I guess neither is the right answer, it just makes two different problems. While we're considering variations, what would that become if the shift size after each step is left as a parameter? $\endgroup$ – Khaur Feb 1 '13 at 12:49bcdefg
irrespective of whethera
andb
were picked or not in the previous step. That is what I had in mind. 2. Shift size as a parameter was my first thought, but I suppose it can be reduced (inefficiently) to a series of increments and decrements. But if a solution with the shift size being a parameter for every operation exists, that would be great too. $\endgroup$ – mayank Feb 1 '13 at 13:02b
and pick it again at the next step? $\endgroup$ – Khaur Feb 1 '13 at 13:05g
is inferior toa
(higher weight and lower cost), anda
was not picked earlier, the new knapsack would be the same as before. $\endgroup$ – mayank Feb 1 '13 at 13:07