dynamic programming and combinatorics - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T20:09:20Z http://mathoverflow.net/feeds/question/35462 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35462/dynamic-programming-and-combinatorics dynamic programming and combinatorics pravesh 2010-08-13T09:51:07Z 2010-08-18T11:53:30Z <p>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.</p> <p>How do we solve it?</p> http://mathoverflow.net/questions/35462/dynamic-programming-and-combinatorics/35478#35478 Answer by falagar for dynamic programming and combinatorics falagar 2010-08-13T11:26:42Z 2010-08-13T11:26:42Z <p>You can use dynamic programming as you suggest in the title.</p> <p>Let $w_{ij}$ be the max gain you can get putting $j$ balls into first $i$ buckets.</p> <p>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})$$</p> <p>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)$.</p> http://mathoverflow.net/questions/35462/dynamic-programming-and-combinatorics/35954#35954 Answer by pravesh for dynamic programming and combinatorics pravesh 2010-08-18T11:53:30Z 2010-08-18T11:53:30Z <p>I tried to work out the problem in a faster way. Here goes my answer. </p> <p>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:</p> <p>$(b_1+b_2\dots +b_{r-1}+b_r)- (d_1+d_2 +\dots d_n)=1$</p> <p>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 </p> <p>$\alpha+b_r=\beta+1$</p> <p>Since $b_r \geq 1$, $\alpha \leq \beta$. </p> <p>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$.</p> <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:</p> <p>$\Delta R(p+1)= \displaystyle \max_{i} { \Delta R(p-i)+ \displaystyle \max_{k \in [1,K]} \Delta l_{k,i}(p)}$</p> <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.</p>