Geek Answers Handbook

The distribution of balls in the "hoppers with given capacities" using dynamic programming

I was wondering how to solve such a problem using DP.

Given n balls and m bins, each bit has a max. capacity c1, c2, ... see. What is the total number of ways to spread these n balls into these m bins.

The problem I am facing is

  • How to find a recurrence relation (I could, when capacitances were the only constant c).
  • There will be several test cases, each of which has its own set of c1, c2 .... see. So, how would DP actually apply all these test cases, because the answer clearly depends on the current c1, c2 .... cm, and I cannot store (or precalculate) the answer for all combinations c1, c2 .... see

In addition, I also could not come up with any direct combinatorial formula for this problem, and I do not think that it exists either.

+7
source share
2 answers

You can define your function by assuming the limits c[0] , c[1] , ... c[m-1] as fixed, and then writing a recursive formula that returns the number of ways you can distribute n balls into cells , starting at index k . With this approach, the basic formula is simply

 def solutions(n, k): if n == 0: return 1 # Out of balls, there only one solution (0, 0, 0, 0 ... 0) if k == m: return 0 # Out of bins... no solutions total = 0 for h in xrange(0, min(n, c[k])+1): # from 0 to c[k] (included) into bin k total += solutions(n - h, k + 1) return total

then you need to add memoization (this will be equivalent to the DP approach) and some other optimizations, for example, for example. that if n > c[k] + c[k+1] + c[k+2] + ... , then you know that there are no solutions without the need for a search (and you can copy partial sums beforehand).

+1
source

  • There is a combinatorial formula for this problem. The problem of finding solutions to your problem is equivalent to finding the number of solutions to the equation
    x1 + x2 + x3 + ... + xm = n
    where xi < ci
    Which is equivalent to finding the cofficient of x^n in the following equation
    (1+x+..x^c1)(1+x+..+x^c2)...(1+x+...+x^cm)

  • The recursion for this equation is quite simple.
    M(i,j) = summation(M(i-1, jk)) where 0<= k <= cj M(i,j) = 0 j <= 0 M(i,1) = i given for every 1= 1 M(i,j) is the number of ways of distributing the j balls in first i bins.

For the Dynamic Programming part Solve this recursion by Memoization, You will get your DP Solution automatically.

+1
source

More articles:


All Articles