Блог

Мне было интересно, как решить такую проблему с помощью DP.

Задано n шаров и m ячеек, каждая ячейка имеет макс. емкость c1, c2, … см. Каково общее количество способов распределения этих n шаров в эти m ячеек.

Проблема, с которой я сталкиваюсь, заключается в

1. Как найти рекуррентное соотношение (я мог, когда все емкости были одной константой c).
2. Будет несколько тестовых примеров, каждый из которых имеет свой собственный набор c1,c2….cm . Итак, как бы DP фактически применялся для всех этих тестовых случаев, потому что ответ явно зависит от текущего c1,c2….cm , и я не могу сохранить (или предварительно вычислить) ответ для всех комбинаций c1,c2….cm .

Кроме того, я не смог придумать какую-либо прямую комбинаторную формулу и для этой проблемы, и я не думаю, что она тоже существует.

Вы можете определить свою функцию, предполагая, что ограничения c[0] , c[1] , … c[m-1] фиксированы, а затем написать рекурсивную формулу, которая возвращает количество способов распределения n шаров в ячейки, начиная с индекса k. При таком подходе базовая формула просто

 def solutions(n, k):
    if n == 0:
        return 1  # Out of balls, there's 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
  

затем вам нужно добавить запоминание (это будет эквивалентно подходу DP) и некоторые другие оптимизации, например, если n > c[k] c[k 1] c[k 2] ... тогда вы знаете, что решений нет без необходимости поиска (и вы можете предварительно вычислить частичные суммы).

1. Для этой задачи существует комбинаторная формула. Задача поиска решений вашей проблемы эквивалентна нахождению числа решений уравнения
   
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)


2. Рекурсия для этого уравнения довольно проста
   
M(i,j) = summation(M(i-1, j-k)) 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.