2
$\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$
2
  • $\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
    Commented May 27, 2018 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$ Commented Nov 15, 2018 at 6:33

1 Answer 1

3
$\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 and acknowledge you have read our privacy policy.

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