Ich habe ein Problem, das so klingt: Wir haben eine Tasche mit Kugeln in. Es gibt R rote Kugeln, B blaue Kugeln und G grüne Kugeln. Ich muss die minimale Anzahl von Extraktionen aus der Tasche finden, so dass ich sicher bin, dass ich mindestens K Bälle der gleichen Farbe haben werde.Drei Arten von Kugeln aus Tasche
Jeder kann mit einer Idee helfen? Oder Tipps, etc?
Wenn K>max(R,G,B) dann hat das Problem keine Lösung. Nehmen wir an, K <= max(R,G,B).
Wenn Sie keine Kontrolle haben, über den Ball extrahiert wird, Sie höchstens brauchen werden (dh das ist eine untere Schranke) min(R, (K-1))+min(G, (K-1))+min(B, (K-1))+1 Extraktionen aus offensichtlichen Gründen: K-1 roten Kugeln extrahieren (oder alle roten Kugeln, wenn R<K), dann extrahiere K-1 grüne Bälle (oder alle grünen Bälle, wenn G<K), und schließlich extrahiere K-1 blaue Bälle (oder alle blauen Bälle, wenn B<K). Jetzt gibt es mindestens einen Ball übrig --- weil max(R,G,B)>=K per Annahme --- und wenn wir es extrahieren haben wir K Bälle der gleichen Farbe. (Dies ist eindeutig der schlimmste Fall.)
Sie brauchen offensichtlich mindestens K Extraktionen (das ist der beste Fall).
Da Sie die Frage mit probability markiert haben, können Sie vielleicht nur einen zufällig ausgewählten Ball gleichmäßig extrahieren. In diesem Fall können wir von der erwarteten Anzahl von Extraktionen sprechen, bevor wir mit K Bällen der gleichen Farbe enden. Das ist eine interessante Frage.
Sie müssen sicherstellen, dass das obere Bindung Arbeits ... Wenn ich die obere Bindung zu testen, bläst sie das int Bereich (I mit Java)
Vielen Dank für Ihre Antwort aus, aber es sieht aus wie es ein besonderes ist Fall auch, ich habe nur 44 Punkte mit deinen Bedingungen ... :) – Vader
@Vader habe ich deine Frage nicht beantwortet? Wenn Sie genauer sind, kann ich die Antwort aktualisieren. – blazs