1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean if the details of the elements in each stack is not known? Please formally define the input and output of the algorithm you want. $\endgroup$ – xskxzr May 27 '18 at 14:46
  • $\begingroup$ what I meant is that, in a stack you really cannot look into any element other than the top. In that case I guess greedy is the only solution possible. But if you know the details of all the elements can you do better. $\endgroup$ – user9712340 Nov 15 '18 at 6:33
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.