用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 

我的問題是，什麼是正確的公式calulate在我的例子中，結果，2種可能性？我如何形成一個正確的公式，所以我有正確的可能性？任何幫助，將不勝感激。 :)

Answer 1

您可以使用動態編程來找到T（N，K），這意味着「我們有多少種方法可以填補到第k個箱子，其中n瓶」 。

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

下面是一個例子實現（使用遞歸，非memoized）在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]) 

Answer 2

您正在尋找所有的非負解到形式的線性方程

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值在一個循環的邏輯。

欲瞭解更多信息ONT他數學參與，看到https://arts-sciences.und.edu/math/_files/docs/courses/supp/math-408/math-408-notes-b.pdf