0

I have a sequence of items $1\leq i \leq n$ that arrive to me one at a time. Each item has a weight $w_i\geq 0$. If I pick up one item, I will not be allowed to pick up any of the next $k$ items ($k< n$). The question is: how can I optimally pick up items, such that the sum of the weights of the chosen items is maximized? There is no other constraint.

The online version of this problem is that I don't know about the weights of the items arriving in the future. The offline version is that I know in advance the weight of every item and their arrival sequence. The problem looks familiar but I am having trouble recall the solution to it. Is there a name/reference for this type of problems? Thanks!

spica
  • 103
  • If you know all the weights, surely you just pick the heaviest one? – GFauxPas Jul 07 '15 at 22:38
  • @GFauxPas: Because then you can't pick up any others for $k\lt n$. It might be better to pick up two nearby items that don't weigh quite as much individually but together weigh more than the weight of the heaviest item. – joriki Jul 07 '15 at 22:40
  • For example, the items are 3,4,5,6,2,5. And k=2. I can choose 3 and 6 which gives me sum=9, or I can choose 5 and 5 which gives me 10. – spica Jul 07 '15 at 22:48

1 Answers1

0

It is a Weighted Interval Scheduling problem.

Example: http://courses.cs.washington.edu/courses/cse521/13wi/slides/06dp-sched.pdf

spica
  • 103