Python - Расчет общих возможностей с использованием рекурсии

Question

Я пытаюсь найти общие возможности размещения 90 яблок в 90 коробках. Любое количество яблок может быть помещено в одну коробку (от 0 до 90 яблок), но все яблоки должны быть помещены в коробки. Я использовал рекурсию, но для завершения расчета потребовалось слишком много времени. Я смог протестировать свой код только с небольшим количеством яблок и коробок. Может ли кто-нибудь помочь мне уменьшить временную сложность моего кода? Заранее спасибо.

import math

boxes = 3
apples = 3

def possibilities(apples, boxes):
    if apples == 0:
        return 1
    if boxes == 0:
        return 0
    start_point = 0 if boxes > 1 else math.floor(apples/boxes)

    p = 0
    for n in range(start_point, apples+1):
        p += possibilities(apples-n, boxes-1)
    return p

t = possibilities(apples,boxes)
print(t)

Answer 1

На мой взгляд, проблема состоит в том, чтобы найти количество отсортированных списков максимум из 90 элементов, сумма которых равна 90.

Существует концепция, которая довольно близка к этому, и мы называем это разделы числа.

Например, разделы 4: [4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1].

После небольшого исследования я нашел эту статью , которая имеет отношение к Ваша проблема.

Как объясняется там, метод рекурсии приводит к очень длинному вычислению для больших чисел, , но ...

Гораздо эффективнее подход через подход, называемый Dynami c Программирование . Здесь мы вычисляем функцию psum (n, k), которая представляет собой общее количество n-разбиений с наибольшим компонентом k или меньше. На любом данном этапе мы вычислим значения psum (1, k), psum (2, k), psum (3, k), ..., psum (n, k) для некоторого фиксированного k. Учитывая этот вектор из n значений, мы вычисляем значения для k + 1 следующим образом:

• psum (i, k + 1) = psum (i, k) + p (i, k ) для любого значения i

• Но напомним, что p (i, k) = Σj p (ik, j) = psum (ik, k)

• Итак, psum (i, k + 1) = psum (i, k) + psum (ik, k)

Таким образом, с небольшой осторожностью мы можем повторно использовать вектор значений и вычислить значения psum (i, k) в скользящем значении для последовательно больших значений k. Наконец, у нас есть вектор со значениями psum (i, n). Значение psum (n, n) является искомым значением p (n). В качестве дополнительного преимущества мы видим, что мы одновременно вычислили значения p (1), p (2), ..., p (n).

В основном, если вы сохраняете промежуточные значения В списке и использовать повторения, представленные в статье,

psum(i,k+1) = psum(i,k) + psum(i-k,k)

вы можете использовать следующую функцию:

def partitionp(n):
    partpsum = [1] * (n + 1)
    for i in range(2, n + 1):
        for j in range(i, n + 1):
            partpsum[j] += partpsum[j - i]
    return partpsum[n]

На каждой итерации внешнего для l oop, список partpsum содержит все значения psum (1, k), psum (2, k), psum (3, k), ..., psum (n, k). В конце итерации вам нужно только вернуть psum (n, n).