Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are $a_i$ balls painted with number $i$. For example if we have balls painted with 1,1,1,3,2. we have $a_1 = 3$, $a_2=1$, $a_3=1$. In total there are $m$ balls painted with number $1,\ldots,n$.

There are $n$ bins. Bin $B_i$ can only contain balls numbered $j$, where $j\leq i$.

Each $B_i$ is associated with a weight $w_i$. $w_i\geq w_j$ if $i\leq j$. The bins have a capacity of $c_i$. $c_i\leq c_j$ if $i\leq j$.

Initially there is 1 ball in $B_1$. The non-empty bin is called the current bin.

Whenever bin $B_i$ is filled(the amount of balls reached the capacity), remove all the balls from $B_i$ and put them in $B_{i+1}$. So there will be only one non-empty bin.

$t_0$ and $k$ are given constants.

We do the following process at step i:

If $t_i=0$, then terminate and return $bw$, where $b$ is the number of balls in the current bin, and $w$ is the weight of the current bin.

Else randomly choose $t_ik$ balls(include the ones in the bin). Return the ones painted with higher number than the current bin and the ones already in the bin, and put the rest in the current bin. The number of newly added balls in this step is $t_{i+1}$.

Intuitively, each ball is randomly attached to $k$ other balls. Putting one in the bin, it will try to "drag" $k$ other balls into the bin. The ball can only "drag" another ball once. The connection breaks afterwards.

The question is:

Given $a_i$, $w_i$, $t_0$ and $k$, compute the set of $c_i$ that maximize the expected return.

I can brute force all possible $c_i$ and see which one turns out the best, but there are $O(m^n)$ possibilities.

The model is so simple I can't help to think is there a simple relation between these variables.

If not, are there faster algorithms than naively try everything?

share|improve this question
Just to be clear: is $t_{i+1}$ the difference between the number of usable balls added at step $i$ and the number of usable balls at the previous step, or is it the number of usable balls added at step $i$? –  Brian M. Scott Sep 30 '11 at 22:28
it's the number of usable balls added at step i. I will change it to make it clear. –  Chao Xu Sep 30 '11 at 22:41
"The model is so simple I can't help to think is there a simple relation between these variables." I dare to disagree. In fact, by the time I'd reached that sentence I was thinking quite the opposite. Also you might want to add some motivation for considering this particular problem; it seems like a rather arbitrary construction to me. –  joriki Oct 1 '11 at 8:41
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.