Collecting weighted items from a dynamic queue

摘要

We consider the problem of collecting weighted items from a dynamic queue S. Before each step, some items at the front of S can be deleted and some other items can be added to S at any place. An item, once deleted, cannot be re-inserted --- in other words, it 'expires'. We are allowed to collect one item from S per step. Each item can be collected only once. The objective is to maximize the total weight of the collected items.