Tất cả sự kết hợp để tạo ra một giỏ trái cây từ cam và táo đã cho

Question

Giả sử bạn được tặng A cam và B táo. Bạn muốn tạo một giỏ tổng số là N trái cây. Tổng số kết hợp táo và cam bạn có thể làm là bao nhiêu?
Giả sử A+B >= N.

Ví dụ:
Tôi có 6 quả cam và 6 quả táo và tôi muốn tạo giỏ với tổng số 9 quả.
Vì vậy, tôi có 4 kết hợp khác nhau:

3 apples 6 oranges 
4 apples 5 oranges 
5 apples 4 oranges 
6 apples 3 oranges 

Tôi muốn tạo ra một thuật toán đơn giản (và hiệu quả) để tính toán con số này.
Có cách nào toán/tổ hợp để tính số này trong O (1) không? Tôi không thể tìm được công thức chính xác cho việc này.

Answer 1

Câu trả lời này sẽ thể hiện cách tổng quát cách nhận đúng công thức đã đóng, thay vì cung cấp công thức "ở đây, hoạt động".

Để có được một công thức chặt chẽ, sử dụng Stars and Bars formula và Inclusion Exclusion, bạn muốn tìm những số giải pháp để phương trình:

x1 + x2 = n 
s.t. 
(1) 0 <= x1 <= A 
(2) 0 <= x2 <= B 

Biểu thị:

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) 

Từ nguyên tắc loại trừ bao gồm, câu trả lời cho vấn đề chúng tôi đã chính thức hóa ở trên là:

E = W(0) - (W(1) + W(2)) + W(1,2) 

Tất cả còn lại là cung cấp công thức cho W(...) và cho điều này, chúng tôi sẽ sử dụng Dấu sao và Thanh.

Sử dụng các phương trình mà không constraits và Định lý 2 quán bar và sao:

W(0) = Choose(N + 2 - 1, 2 - 1) = Choose(N + 1, 1) = N + 1 

Để tính toán W (1) và W (2), chúng tôi buộc x1/x2 là A+1 hoặc B+1, và sau đó đi như bình thường , và nhận được phương trình:

x1 + x2 = N - A - 1 
x1 + x2 = N - B - 1 

và số lượng các giải pháp được (một lần nữa sử dụng định lý 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} 

Đối với W (1,2), chúng tôi đặt cả và tiếp tục và nhận được:

W(1,2) = Choose(N - A - 1 - B -1 + 2 - 1) = Choose(N-A-B-1,1) = max{N-A-B-1,0} 

Tóm nó tất cả cùng nhau đến công thức thức:

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} 

nào trong ví dụ của bạn là:

E = 9 + 1 - 3 - 3 + 0 = 4 

Answer 2

Ok, xin lỗi, tôi đã (đường) quá nhanh.

Bạn biết luôn có ít nhất một giải pháp.

Bạn phải lấy ít nhất đủ trái cây của A sao cho với B, nó làm cho N. Bạn lấy tối đa A quả A. Nếu lớn hơn N, giới hạn là N. Vì vậy, câu trả lời phải là:

min(A, N) - max(0, N-B) + 1 

Answer 3

Nó phải là

ans = (A + B) - N + 1 

Answer 4

phép nói rằng A_max là tối đa số A có thể được bao gồm trong sự kết hợp, và A_min là số nhỏ nhất của A mà phải được bao gồm trong bất kỳ sự kết hợp. Sau đó, sẽ có hai điều kiện đó phải được Satisified:

1. A_max + B_min = N
2. A_min + B_max = N

Vì chúng ta biết A_max (đó là min(NumOfA, N)), B_min có thể tìm thấy dễ dàng từ phương trình đầu tiên. Tương tự, người ta có thể tìm thấy A_min từ phương trình thứ hai. Do đó, danh sách các tổ hợp sẽ là:

A_max + B_min

(A_max-1) + (B_min+1)

(A_max-2) + (B_min+2)

...

(A_min) + (B_max)

Vì vậy, số lượng kết hợp như vậy sẽ (A_max - A_min + 1) hoặc là (B_max - B_min + 1)