Angenommen, ich habe eine Matrix A der Größe n x p mit n > p, jedes Element 0 <= A <= 1. Ich würde gerne Elemente in A finden, eine in jeder Spalte, so dass die Gesamtsumme maximiert ist und jedes Element in einer anderen Zeile ist. Daher sind n permute p verschiedene Kombinationen zu berücksichtigen. Gibt es einen Namen für dieses Problem? Ich habe solche gefunden wie das Rucksackproblem, aber das Setup ist anders. Sind sie irgendwelche effizienten Algorithmen, um das zu berechnen, zum Beispiel n=300, p=10? Es gibt ein paar spezielle Fälle zu prüfen, zum Beispiel wenn das Maximum in jeder Spalte in einer anderen Zeile ist. Ansonsten bin ich auf dynamische Programmierung angewiesen? Vielen Dank!Maximierung der Summe bei unterschiedlichen Indizien
1
A
Antwort
1
Dies ist maximum matching in a weighted bipartite graph, auch bekannt als assignment problem. Spalten und Zeilen sind Graphteile (bzw. Agenten und Aufgaben) und Zellen sind Kanten (bzw. Aufgabenzuweisungen).
Dies wird effektiv durch die Hungarian algorithm gelöst, die Polynom ist.
Verwandte Themen
- 1. Matlab: Maximierung der Summe der Logarithmen
- 2. Maximierung der Aktienrendite bei mehreren Aktien
- 3. Summe der Transaktionen zwischen unterschiedlichen Terminen
- 4. Maximierung der arithmetischen Ausdruck
- 5. Neupositionieren von Air NativeWindow bei Maximierung?
- 6. Apache Common SimplexSolver ObjectiveFunction für die Maximierung der Summe der Werte in einer Matrix
- 7. Randomized Algorithm Wahrscheinlichkeits-Maximierung
- 8. Maximierung der Speichernutzung für einen MySQL-Analyseserver
- 9. brauchen Hilfe bei der Auswahl unterschiedlichen Einträgen
- 10. Postgresql: Wählen Summe mit unterschiedlichen Bedingungen
- 11. Zeichnen Sie nur eine Indizien von IBO
- 12. Maximierung der Java-Anwendung (Vanille Datenverarbeitung) Leistung
- 13. Maximierung nach einer Funktion
- 14. Gelegentlicher Konvertierungsfehler bei Verwendung der Funktion SUMME
- 15. Maximierung des Gewinns mit DP?
- 16. Größe JFreeChart.ChartPanel auf Maximierung Bildschirm
- 17. Summe der Summe finden
- 18. Kumulative Summe einer Division mit unterschiedlichen Nennern R
- 19. C++ Fehler bei der Summe der ganzen Zahlen
- 20. Erhalten der Summe der Summe mit Unterabfrage
- 21. Algorithmus zur Maximierung der Produktsumme von Elementen zweier Arrays
- 22. C++ Algorithmus für die in der linearen Programmierung lösen Maximierung
- 23. Summe von zwei identisch großen HLists bei der Kompilierzeit?
- 24. DataSource nach Maximierung des Fensters in WPF
- 25. Berechnen der Summe der Optionsfelder, Anzeigen der Summe und Weiterleiten an externen Beanstream-Server
- 26. Wie berechnet man die Summe bei Änderung?
- 27. Oracle SQL Reset läuft Summe bei Null
- 28. Summe Summe der 2D-Array-Werte C#
- 29. Fehler während Summe der Summe in LINQ
- 30. Stop-Summe bei bestimmten Anzahl Google Sheets
Dies ist [maximale Übereinstimmung in einem gewichteten bipartiten Graphen] (https://en.wikipedia.org/wiki/Matching_ (graph_theory) #In_weighted_bipartite_graphs). Spalten und Zeilen sind Diagrammteile und Zellen sind Kanten. –
@ n.m. Es scheint, dass der ungarische Algorithmus ziemlich gut für die Dimensionen funktioniert, denen ich gegenüberstehe. Bitte posten Sie Ihren Kommentar als Antwort, damit ich ihn annehmen kann. – Almacomet