Suche maximale Anzahl der Sätze, die erfüllt bestimmte Bedingung ist

einige Reihen von Zahlen gegeben:Suche maximale Anzahl der Sätze, die erfüllt bestimmte Bedingung ist

156, 434, 600

Wie die maximale Anzahl von Gruppen zu finden, die mehr als 500 ist? Es ermöglicht Ihnen, eine Gruppe mit nur einem Element zu erstellen. Es ist jedoch nicht erlaubt, ein Element wiederholt unter Gruppen zu verwenden. Also, in dem obigen Beispiel ist die Antwort:

2 // {156, 434}, {600}

Ich hoffe, dass ein allgemeiner Algorithmus machen kann es anwenden, wenn ich einen anderen Satz erhalten von Zahlen, die unterschiedliche Größe haben.

156, 434, 600
642, 324, 174, 100, 452
174, 100, 455, 900, 1200, 341

Aber ich weiß nicht, wo Soll ich anfangen? Also, bitte hilf mir, eine gute Idee zu bekommen.

Quelle

2017-12-29 sangjoon moon

Was ist mit der Gruppe {156,334,600} selbst, die> 500 ist, gibt es 3 Antworten? {156, 334}, {600} und {156,334,600}? –

Einmal verwendet, können die Nummern nicht wiederverwendet werden?In Anbetracht Ihres Beispiels können wir das nicht, aber die Maximierung der Anzahl von Gruppen führt zu {600} oder {156, 600} oder {334, 600} oder {156, 334, 600}. Warum ist {156, 334} auch eine gültige Antwort, wenn die Summe 490 ist? – valcanaia

Sie wollen das nicht. Weil die Anzahl der Gruppen in der Größe der Eingabe exponentiell sein kann. Zumindest wenn Ersatz erlaubt ist. – Yola

Eine Möglichkeit könnte von der Anzahl der Bins die beste Lösung für binäre Suche sein, jedes Mal eine Polynom-Zeit Approximationsschema für die Multiple Subset Sum Problem (wie https://www.researchgate.net/publication/262408639_The_Multiple_Subset_Sum_Problem) verwendet wird.

_{1. Das Mehrfachsatz-Summenproblem; Alberto Caprara, Hans Kellerer und Ulrich Pferschy; SIAM Journal auf Optimierung Vol. 11: Problem. 2: Seiten. 308-319 (Ausgabe Veröffentlichungsdatum: 2000)}

Quelle

2017-12-30 12:03:11

Ich bin ziemlich sicher, dass dieses Problem NP-Hard ist. Das nächste Problem, das ich mir gerade vorstellen kann, ist das bin packing problem, in dem Sie die Anzahl der Bins B (von gleicher Größe V) minimieren möchten, die notwendig sind, um n Elemente unterschiedlicher Größe anzupassen.

In Ihrem Fall sollten Sie die Anzahl der Bins maximieren, die minimal mit einer Größe von V. gefüllt sind

Als Annäherung Sie die gierige Strategie der Bin Packing Problem anpassen konnte.

1) Sort your set of numbers in descending order. 

2) Place all numbers larger than 500 in a seperate group 

3) Open a new empty group 

4) Find the smallest number that increases the sum of the current open group over 500. 
    If such a number exists, put this number in the current open group jump to 3) 
    If no such number exists select the largest number not yet used and place it in the open group and repeat 4)

Beispiel:

174, 100, 455, 900, 1200, 341

nach

Sortier

1200, 900, 455, 341, 174, 100

resultierende Gruppen

{1200}, {900}, {45 5, 100}, {341, 174}

Quelle

2018-01-02 10:17:45 SaiBot

Suche maximale Anzahl der Sätze, die erfüllt bestimmte Bedingung ist

Antwort

Verwandte Themen