Ich habe eine Reihe von Elementen in einem Array, die jeweils einem bestimmten Gewicht zugeordnet sind. Es gibt eine Geschäftsregel, die besagt, dass zwei benachbarte Elemente kein Gesamtgewicht von mehr als einem bestimmten Wert haben dürfen, sagen wir 100 zur Vereinfachung.
Zum Beispiel ist das Folgende in Ordnung:
%Vor%Aber nicht dieser (seit 50 + 60 = 110)
%Vor%Ich versuche, einen Algorithmus zu implementieren, der (wenn möglich) die Elemente neu anordnet, damit die Geschäftsregel erfüllt wird. Zum Beispiel könnte die zweite neu angeordnet werden [60,40,50] oder [50,40,60]
Der Algorithmus sollte auch versuchen, die Anzahl der bewegten Objekte zu minimieren, d. h. die erste obige Lösung ist am geeignetsten, da die "Subpermutation" [60, 40] beibehalten wird.
Ich bin nicht auf der Suche nach einer vollständigen Antwort oder nach Codebeispielen, würde mich aber freuen, wenn jemand zu diesem Zweck einige Algorithmen oder Kategorien von Algorithmen aufzeigen könnte. Es wäre viel besser, sich auf einen existierenden und bewährten Algorithmus zu verlassen als auf selbstgemachte Sachen;)
Hinweis: In Wirklichkeit ist die Anzahl der Elemente sehr groß, daher ist das Testen aller verschiedenen Permutationen KEINE Option.
Nette gierige Lösung: für den ersten Platz nehmen Sie die maximale Anzahl. Für jeden nächsten Platz nehmen Sie maximal aus nicht genommenen Zahlen, die Ihrem Zustand entsprechen. Wenn Sie alle Nummern platzieren, haben Sie eine Lösung gefunden. Sonst existiert die Lösung nicht, warum - es ist eine Übung für dich.
Mein Beweis: Stellen Sie sich vor, eine Lösung existiert. Zeige, dass mein Algorithmus es finden wird. Let's a_1, ..., a_n - jede Lösung. Sei a_i - maximales Element. Dann ist a_i, a_ {i-1}, ..., a_1, a_ {i + 1}, a_ {i + 2}, ..., a_n auch eine Lösung, weil a_1 & lt; = a_i, a_1 + a_ {i + 1} & lt; = a_i + a_ {i + 1}, so (a_i, a_ {i + 1}) ist ein gutes Paar. Als nächstes sei a_1, ..., a_j ein Element gemäß meiner Lösung. Zeige, dass a_ {j + 1} ein Element sein kann, wie es meine Lösung annimmt. Sei a_i - Maximum von a_ {j + 1}, .., a_n. Dann ist a_1, ..., a_j, a_i, a_ {i-1}, ..., a {j + 1}, a_ {i + 1}, ..., a_n auch eine Lösung. Es zeigt, dass Algo immer eine Lösung findet.
Große Gegenstände können nur neben kleinen Gegenständen sein.
Beispiel: [1,3,8,4,2,4,1,7]
Ich bin mir ziemlich sicher, dass du es nicht besser machen kannst. Wenn die Geschäftsregel trotzdem verletzt wird, gibt es keine Lösung. Beweisen / Gegenbeispiel links als Übung; -)
Bearbeiten: Nimm den größten Gegenstand zuerst!
Sieht ähnlich aus wie ein Bin-Packing-Problem, werfen Sie einen Blick auf (zB) Ссылка
Ich bin mir ziemlich sicher, dass es nicht das gleiche ist, aber es kann Ihnen einige Hinweise geben.
Sie müssen auch überlegen, was passieren würde, wenn ein einzelnes Element über dem Limit liegt - wie würden Sie damit umgehen?