4
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ What happens if you pick the first element? When you shift the set of available items, do you then remove the second item, or do you remove the first, now useless item? Say at one step, you have items abcdef (in that order) to pick from; if you choose to pick a, at the next step do you get to pick from bcdefg or from cdefg? 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:49
  • $\begingroup$ @Khaur 1. After the shift, the knapsack is considered empty, and the input becomes the new list. So, you pick from bcdefg irrespective of whether a and b 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:02
  • $\begingroup$ Does that mean you can pick b and pick it again at the next step? $\endgroup$ – Khaur Feb 1 '13 at 13:05
  • $\begingroup$ @Khaur Yes, you can. So if say g is inferior to a (higher weight and lower cost), and a was not picked earlier, the new knapsack would be the same as before. $\endgroup$ – mayank Feb 1 '13 at 13:07
  • $\begingroup$ When I first read your question, I didn't get that the shift occurs between full knapsacks problems. I was considering a single knapsack problem where the pool of items changes after each picked item. I'll dig a bit into this other one, and maybe later expand it into a question of its own. $\endgroup$ – Khaur Feb 1 '13 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.