假设给你A橙子和B苹果。你想要创建一个装满N水果的篮子。你能做出的苹果和橘子组合的总数是多少?
假设A+B >= N
例子:
我有6个橙子和6个苹果，我想创建一个总共有9种水果的篮子。
所以我有4种不同的组合:
3 apples 6 oranges
4 apples 5 oranges
5 apples 4 oranges
6 apples 3 oranges
我想创建一个简单(高效)的算法来计算这个数字。
是否有数学或组合的方法来计算O(1)中的这个数?我找不到正确的公式
这个答案将展示如何得到正确的封闭公式的一般方法，而不是给出"这里，它有效"的公式。
要得到一个接近的公式，使用星形条形公式和包含排除，您需要找到方程的解的数量:
x1 + x2 = n
s.t.
(1) 0 <= x1 <= A
(2) 0 <= x2 <= B
表示:
W(0) = #solutions to the problem regardless of restrictions
W(1) = #solutions to the problem with (1) is NOT correct (x1 > A)
W(2) = #solutions to the problem with (2) is NOT correct (x2 > B)
W(1,2) = #solutions to the problem with both (1,2) NOT correct (x1 > A and X2 > B)
根据包含不相容原理，我们对上述问题的形式化的答案是:
E = W(0) - (W(1) + W(2)) + W(1,2)
剩下的就是给W(...)提供公式，为此我们将使用星形和条形。
用无约束方程和条形星形定理2:
W(0) = Choose(N + 2 - 1, 2 - 1) = Choose(N + 1, 1) = N + 1
为了计算W(1)和W(2)，我们强制x1/x2为A+1或B+1，然后像往常一样，得到方程:
x1 + x2 = N - A - 1
x1 + x2 = N - B - 1
和解的个数是(再次使用定理2):
W(1) = Choose(N - A - 1 + 2 - 1, 1) = Chose(N-A,1) = max{N-A,0}
W(2) = (similarly) = max{N-B,0}
对于W(1,2)，我们同时设置它们，然后继续得到:
W(1,2) = Choose(N - A - 1 - B -1 + 2 - 1) = Choose(N-A-B-1,1) = max{N-A-B-1,0}
将这些加起来得到最终公式:
E = W(0) - (W(1) + W(2)) + W(1,2) =
= N + 1 - max{N-A,0} - max{N-B,0} + max{N-A-B-1,0}
在你的例子中是:
E = 9 + 1 - 3 - 3 + 0 = 4
设A_max是组合中可以包含的A的最大值，A_min是任何组合中必须包含的A的最小值。那么有两个条件必须满足:
-
A_max + B_min = N -
A_min + B_max = N
因为我们知道A_max(即min(NumOfA, N))，所以从第一个方程可以很容易地找到B_min。同样地，我们可以从第二个方程中找到A_min。因此，组合列表将是:
A_max + B_min
(A_max-1) + (B_min+1)
(A_max-2) + (B_min+2)
…
(A_min) + (B_max)
这样的组合计数将是(A_max - A_min + 1)或(B_max - B_min + 1)
应该是
ans = (A + B) - N + 1
好吧，对不起，我太快了。
你知道总会有至少一个解决方案。
你至少要取足够多的A的果实使B等于N，你取A的最大果实A如果它大于N，极限是N，所以答案应该是
min(A, N) - max(0, N-B) + 1