三種袋子球類型

Question

我有一個問題，聽起來像這樣： 我們有一個袋子有球。有R紅球，B藍球和G綠球。 我需要從袋子中找到最少數量的提取物，以便我確信至少有K個相同顏色的球。

任何人都可以幫助任何想法？或提示等？

Answer 1

如果K>max(R,G,B)那麼問題沒有解決方案。所以我們假設K <= max(R,G,B)。

如果你沒有對哪個球被提取的任意控制，你需要最多（即這是一個下界）min(R, (K-1))+min(G, (K-1))+min(B, (K-1))+1提取原因很明顯：提取K-1紅球（或全部紅球，如果R<K），然後提取K-1綠球（或者所有綠球，如G<K），最後提取K-1藍球（或所有藍球，如果B<K）。現在至少有一個球剩下---因爲max(R,G,B)>=K由假設---當我們提取它時，我們有K相同顏色的球。 （這顯然是最糟糕的情況。）

您顯然至少需要K提取（這是最好的情況）。

由於您用probability標記了問題，也許您只能隨機抽取一個統一的球。在這種情況下，我們可以談談所需的提取次數，然後才能得到顏色相同的K球。這是個有趣的問題。

Answer 2

您需要確保上結合工作......當我測試的上鍵，它吹掉INT範圍（我用java）