Maximizing the sum from m stacks using k pop's Assume you have m stacks each some elements within it. If you are allowed to do k pops , the objective is to maximize the sum(sum increases by the value of the popped element). What is the best algorithm which would be able to solve this problem.
Can the complexity be improved if the details of the elements in each stack is known beforehand.
You can use dynamic programming to solve this problem in polynomial time.
Create a table $A[i,l]$ with $0\le i \le m$ and $0\le l\le k$, where $A[i,l]$ reprensents the optimal allocation using at most $l$ pops among the first $i$ stacks. We initiate by $A[.,0]=A[0,.]=0$ and we have the following inductive step :
$$
A[i+1,l]=\max\left\{A[i,l-t]+(t \text{ pops from stack } i+1), 0\le t \le l\right\}
$$
We can compute $A[m,k]$ in time $O(k^2m)$.