You have a chain of pieces of jewelry. There are thousands ($N$) of pieces chained one next to the other. Each piece of jewelry has associated value $p_i$
A lot of the pieces of jewelry have negative value. So $p_i$ can be less than zero.
You know the exact values of all pieces and their location in the chain too. This is not a stochastic problem.
You have a knife and you can cut anywhere, you put the first segment of jewels in bag A, then you make another cut, put the next jewels in bag B, then make another cut, put that in bag A again, the next segment in bag B and so on. You keep going on for a maximum of M times making cuts. You can choose one of the bags to take with you and throw away the other. Notice that you don't get to keep consecutive segments of the chain.
The question is where do you cut in order to maximize the value of the segments you keep?
I created a program to solve this, but I was wondering if there is something else out there. My solution requires sophisticated software. I gave it a try and I converted it to a binary optimization program which anyone could solve with a MIP tool.
maximize: $ \displaystyle \sum_{i=1}^N p_i \beta_i $
subject to: $\displaystyle \sum_{i=1}^{N-1} | \beta_{i+1} - \beta_i| \leq M$
$\beta_i \in \{0, 1\}, \; \forall i = \{1, ..., N\}$