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.

How do we solve it?

-

You can use dynamic programming as you suggest in the title.

Let $w_{ij}$ be the max gain you can get putting $j$ balls into first $i$ buckets.

Then $w_{ij}$ has the following recursive relation: $$w_{i,j} = \max_{0 \le t \le \min(N-1, j)}(w_{i-1,j-t} + \Delta l_{i, t})$$

There $t$ is the number of balls you put into $i$-th bucket. Hence you can calculate $w_{K, \lambda}$ (your answer) in time $O(K \lambda N)$.

-
 True. This is the right answer. However, it is far too complex. i have come up with a simpler one. which will select the bucket at every iteration (ball being added). Here is the recursion. $\Delta R(p+1)= \displaystyle \max_{i} \{ \Delta R(p-i)+ \displaystyle \max_{k \in [1,K]} \Delta l_{k,i}(p)\}$ Here, $R(p+1)$ is the optimal gain in putting p+1 balls. Can you comment if it is optimal? – pravesh Aug 13 2010 at 11:45 Is $R(p)$ the optimal gain in putting $p$ balls considering all the buckets? If so then I don't understand your formula. If you have put $i$ balls into $k$-th bucket you can't use this bucket any more. – falagar Aug 13 2010 at 11:50 And I don't know if there exists faster solution. – falagar Aug 13 2010 at 11:52 Yes if you have put i balls in the kth bucket, you can only fill the bucket with remaining N-i balls. Btw, you can also take them out if there is a better solution in the later stages. In this solution, I am filling one ball at a time by finding the right bucket for that ball. Now since each bucket can be filled with N-1 balls, I am also exploring that dependency by going back p−i times, where i <= N. Does it make sense? – pravesh Aug 13 2010 at 12:10

I tried to work out the problem in a faster way. Here goes my answer.

Let the set ${\chi_p}={t_i, 1 \leq i \leq l_p }$ collects indices of the buckets for optimally filling $p$ balls. $\bar{\chi_p}={1,\dots,K}/ \chi_p$ is the set of buckets not participating in the $p$ allocations. The DP we propose derives from the fact that while going inductively from $p$ to $p+1$ allocations, we do not add more than one element (bucket) from the set $\bar{\chi_p}$. Hence, at every stage of the DP, the goal is to identify bucket that needs to be added and the number of balls to be put in the selected bucket in order to maximize the resulting overall gain. We prove this property. \subsubsection{Proof} Let us assume that while going from the stage $p$ to $p+1$, we add $r$ new buckets from the set $\bar{\chi_p}$ into $\chi_{p+1}$ with indices $x_1,\dots,x_r$ containing $b_1,\dots,b_r$ balls. The corresponding gain accrued from the added buckets are $g_i, \, i \in {1,\dots,r}$. We also alter the allocation in $n$ buckets from $\chi_p$ with indices $y_1,\dots,y_n$ removing $d_1,\dots,d_n$ balls respectively. Similarly, let the total loss due to this alteration be $q$. Since we add one ball while going from $p$ to $p+1^{th}$ stage, following is true:

$(b_1+b_2\dots +b_{r-1}+b_r)- (d_1+d_2 +\dots d_n)=1$

Let $\alpha = b_1+b_2\dots +b_{r-1}$, be the total number balls placed in all the added buckets except the $r^{th}$ bucket of index $x_r$. Similarly, let $\beta= (d_1+d_2 \dots +d_n)$ total number of balls removed from the set $\chi_p$ while transitioning from $p^{th}$ to $p+1^{th}$ allocation. By

$\alpha+b_r=\beta+1$

Since $b_r \geq 1$, $\alpha \leq \beta$.

Now, consider the partition of the total removed balls $\beta$ such that $\beta=\alpha + \epsilon, \, \epsilon \geq 0$. The loss $q$ can also be partitioned as $q = q_{\alpha}+ q_{\epsilon}$, such that $q_{\alpha}$ is maximum. The gain due to the allocation of $\alpha$ balls in $p+1^{th}$ step in new buckets is $\sum_{i=1}^{r-1} g_i$. It cannot be less then $q_{\alpha}$ else, it is not optimal, as there exists an allocation with higher gain. This implies $\sum_{i=1}^{r-1} g_i \geq q_{\alpha}$. Moreover, $q_{\alpha}$ was a part of optimal solution of $p$ allocations. Hence, using same argument, $q_{\alpha} \geq \sum_{i=1}^{r-1} g_i$. This means $\sum_{i=1}^{r-1} g_i = q_{\alpha}$. This is only possible when $x_1,x_2\dots, x_{r-1} \in \chi_p$. This implies that no more than one bucket is derived from $\bar{\chi_p}$ in the $p+1^{th}$ step. Note that it is also possible that the $p+1^{th}$ ball is allocated to $\chi_p$.

The DP approach is based on the above property. Given that we know the optimal allocation for $p$ balls, and optimal gains for $1,2\dots,p$ allocations, we can approach the $p+1^{th}$ by exploiting these optimal substructures. Let us call the $K \times N-1$ matrix $\Delta {\bf L}$ whose elements are $\Delta l_{k,i}$ as gain matrix. Let the optimal gain and corresponding updated gain matrix after $p$ allocations be $\Delta R(p)$ and $\Delta {\bf L}(p)$ respectively. Since, at most one bucket is picked at every step, and this bucket has the capacity of $N-1$, hence 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)}$

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.

-