用 3 个常数计算可能性的算法？

Question

我想计算将一些随机瓶子放入板条箱中的可能性有多少。我得到三个常量。

N = Count of Bottles
k = Count of Crates
K[num] = How many Bottles fit inside ONE Crate

示例：

N = 7; // 7 Bottles
k = 2; // 2 Crates
K1 = 3; // Crate 1 -> max 3 Bottles
K2 = 5; // Crate 2 -> max 5 Bottles

Above equals to 2 Possibilities:
1: First Crate 1 -> 3 bottles, Second crate -> 4 Bottles
2: First Crate -> 2 bottles, Second crate -> 5 Bottles

我的问题是，在我的例子中计算结果的正确公式是什么，即 2 种可能性？我怎样才能形成正确的公式，所以我得到正确的可能性？任何帮助，将不胜感激。 :)

Answer 1

您正在寻找形式为

的线性方程的所有非负解

x[1] + x[2] + . . . + x[k] = N

和0 <= x[i] <= K[i]

其中 x[i] 是板条箱中的瓶子数量 i

我相信这是组合学中 Real Donut Shop Problem 的一个例子。数学 SE 上也有类似的问题。

https://math.stackexchange.com/questions/223345/counting-donuts

由于您需要实际显示结果，因此这些信息应该足以在满足方程式的所有可能的 X 值集合的循环中实现逻辑。

有关所涉及的数学的更多信息，请参阅https://arts-sciences.und.edu/math/_files/docs/courses/supp/math-408/math-408-notes-b.pdf

Answer 2

你可以使用动态规划求出T(n, k)，即"how many ways we can fill up to the kth crate with n bottles"。

T(0, 0) = 1
T(n, 0) = 0
T(n, k) = sum{1<=i<=K[k], T(n-i, k-1)}

这是 Python 中的示例实现（使用递归，非记忆化）：

def T(n, k, K):
    if k==0: return n==0
    return sum(T(n-i, k-1, K) for i in xrange(1, K[k-1]+1))

print T(7, 2, [3, 5])

用 3 个常数计算可能性的算法？

Algorithm to Calculate Possibilities with 3 Constants?

algorithm

math

permutation

combinatorics