Verilen portakal ve elmalardan bir meyve sepeti oluşturmak için tüm kombinasyon

Question

A portakalları ve B elmaları verdiğinizi varsayalım. Toplam N meyveleri bir sepet oluşturmak istiyorsunuz. Elmalar ve portakalların toplam kombinasyon sayısı nedir?
A+B >= N varsayarsak.

Örnek:
Ben 6 portakal ve 6 elma var ve toplam 9 meyve ile bir sepet oluşturmak istiyorum.
Yani 4 farklı kombinasyonları vardır:

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

Ben bu sayıyı hesaplamak için basit (ve verimli) algoritması oluşturmak istiyorum.
Bu sayıyı O (1) cinsinden hesaplamak için herhangi bir matematiksel/birleştirici yöntem var mı? Bunun için doğru bir formül bulamadım.

Answer 1

Bu yanıt, "burada çalışır" formülünü vermek yerine, doğru kapalı formüle nasıl ulaşılacağını genel bir şekilde gösterecektir.

Stars and Bars formula ve Inclusion Exclusion kullanarak, yakın bir formüle almak için, denklemin çözüm sayısını bulmak istiyoruz:

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

Göstermek:

alma ve dışlama prensibi itibaren

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) 

, Yukarıda resmileştirdiğimiz sorunun cevabı:

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

Tümü, W(...)'a formüller vermek içindir ve bunun için Yıldızlar ve Çubuklar'ı kullanacağız. Kısıtlar ve barlar ve yıldızların Teorem 2 olmadan denklemler kullanılarak

:

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

W hesaplamak için (1) ve W (2), biz her zamanki gibi gidip sonra A+1 veya B+1 olmak ve x1/x2 zorlamak

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

ve çözeltiler sayısı (yine teoremi 2 kullanılarak) vardır:

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

ve denklemler elde W için

(1,2) biz de ayarlayabilir ve gidip alıyorum:

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} 

sizin örnekte olduğu: nihai formül birlikte

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

hepsini özetleme:

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

Answer 2

Tamam, üzgünüm, çok hızlıymışım.

Her zaman en az bir çözüm olduğunu biliyorsunuz.

En azından yeterli A meyvesini almanız gerekir, böylece B ile N yapar. En fazla A aldığınız bir A meyvesi. N'den büyükse, sınır N'dir. Yani cevap şu şekilde olmalıdır:

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

Answer 3

O

ans = (A + B) - N + 1 

Answer 4

A_max kombinasyon dahil edilebilir A sayısının maksimum Diyelim olmalı ve A_min herhangi bir kombinasyonu dahil edilmelidir A en az sayı. Sonra satisified gereken iki koşul olacaktır: Biz (min(NumOfA, N) olan) A_max bildiğimiz için

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

, B_min ilk denklemden kolayca bulunabilir. Benzer şekilde, ikinci denklemden A_min'u bulabilirsiniz. Sonuç olarak, kombinasyonların listesini olacaktır:

(A_max-2) + (B_min+2)

A_max + B_min

(A_max-1) + (B_min+1)

...

(A_min) + (B_max)

Yani böyle kombinasyonların sayısı (A_max - A_min + 1) olurdu veya (B_max - B_min + 1)