The issue

Given $n$ stacks of $ok$ integers every. What’s the most sum that may be achieved by eradicating precisely $p$ integers?

The next instance illustrates the issue.

$n$ = 3, $ok$ = 4, $p$ = 3

stack 1: 2, 5, 12, 5

stack 2: 10, 3, 12, 50

stack 3: 7, 4, 20, 20

Notice that the highest of a stack is the leftmost aspect.

Right here, the optimum resolution is to choose all the primary three numbers from stack 3, which supplies a sum of 31.

The algorithm

I got here up with the next algorithm.

The concept is to calculate the very best sum for every stack if all $p$ parts had been chosen from that individual stack. This sum solely considers the integers that may probably be taken.

Then, greedily take the highest aspect from the stack with the very best sum. And replace the sum for all stacks as a result of now solely $p-1$ integers should be popped.

The query

is that this algorithm all the time going to supply an accurate reply? If not, when would this fail?

Disclaimer

I’m conscious {that a} dynamic programming resolution can resolve the issue in $O(npk)$ time.