Suppose there are $ K $ buckets each can be filled upto $ N-1 $ balls. The gain on putting $ i $ balls in the $ k^{th} $ bucket is given by $ \Delta l_{k,i}, \, i \in [1,N-1] $. The problem is to put $ \lambda $ balls in those buckets to maximize the overall gain.
This is how I solved it. I am not sure if the approach is optimal. Ans: Lets call the $ K \times N-1 $ matrix $ \Delta {\bf L} $ whose elements are $ \Delta l_{k,i} $ as gain matrix. \par To arrive at the DP structure of the problem,
How do we use induction. Let the optimal gain and corresponding updated gain matrix after $ p $ allocations be $\Delta R(p)$ and $\Delta {\bf L}(p)$ respectively. My algorithm is based on the fact that every successive allocation is dependent only on previous $N-1$ decisions. It can be written as follows:
\Delta R(p+1)= \displaystyle \max_{i} { \Delta R(p-i)+ \displaystyle \max_{k \in [1,K]} \Delta l_{k,i}(p)} \label{Dp_2}
At every step, the recursion involves choosing the optimal bucket and number of balls to be put in solve itsuch that new total gain is maximized.?
