2 shortened the problem

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.?

1

# dynamic programming and combinatorics

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, 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 it such that new total gain is maximized.