Распределение шаров в «бункеры с заданными емкостями» с использованием динамического программирования

Question

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

Учитывая n шаров и m бинов, каждый из которых имеет макс.емкость с1, с2, ... см.Каково общее количество способов распределения этих n шаров в эти m бинов.

Проблема, с которой я сталкиваюсь, состоит в следующем:

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

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

Answer 1

Вы можете определить свою функцию, предполагая ограничения 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] + ..., то вы знаете, что нетрешения без необходимости поиска (и вы можете предварительно вычислить частичные суммы).

Answer 2

1. Существует комбинаторная формула для этой задачи. Задача нахождения решения вашей задачи эквивалентна нахождению числа решений уравнения
   x1 + x2 + x3 + ... + xm = n<br/> where xi < ci<br/> Which is equivalent to finding the cofficient of x^n in the following equation<br/> (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.</p></li> </ol> <p>For the Dynamic Programming part Solve this recursion by Memoization, You will get your DP Solution automatically.<br>