Bestimmte Summe aus Mehreren Werten

[hrkplmstr]

Hallo zusammen,

bin ganz neu hier und stehe vor einer für mich schwierigen Aufgabe:

Ich muss verschiedene Werte zu einer Maximalsumme von 553 ( oder zumindest nah dran) zusammenführen.

Ich habe 86 verschiedene Werte und aus diesen müssen jedesmal ohne die schon verwendeten Werte erneut 553 als Maximalsumme gebildet werden.

Die Datei mit den Werten habe ich angehängt. Die Gelb gefärbten Zeilen sind die Werte aus denen 553 gebildet werden müssen

Vielleicht gibt es hierfür eine Formel oder eine Lösungsmöglichkeit?

Vielen Dank im Voraus!


Viele Grüße

[Ego]

Hallo h...,

aus meiner Sicht fehlen da einige Zusatzziele wie:

maximale Anzahl an Elementen pro Kombination,
minimaler Summenwert,
eventuell möglichst viele Kombinationen
...

Mit deinen Zahlen gibt es Milliarden von Kombinationen eine Summe zwische 447 und 553 zusammenzustellen.
Allein wenn ich nur die Kombinationen aus 2-5 Elementen ermittle sind es 235.592 Möglichkeiten (benötigt auf meinem Rechner ca 40 Sekunden).

[hrkplmstr]

Hallo, 

die Maximale Anzahl an Elementen ist vollkommen egal. egal ob ich mit 2 Werten die 553 erreiche oder mit 20.

der Minimalesummenwert ist eigentlich der restbetrag aus den werten die nicht mehr 553 ergeben.

Die Anzahl der Kombinationen sollte möglichst klein gehalten werden.


Im Endeffekt muss ich Reifen in einen Container packen und dieser hat 564kubikmeter. Die Maximal auslastung darf aber nur 553 kubikmeter betragen. 

Was ich brauche bzw hoffe zubekommen ist eine Formel die mir meine Werte so aufteilt dass jedesmal 553 entsteht dabei aber die schon benutzten mengen nicht berücksichtigt oder farblichmarkiert.

Grüsse

[Ego]

Hallo h...,

in der Anlage einmal eine programmierte Lösung mit der ich versuche möglichst häufig mit wenigen Werten sehr nahe an den gesuchten Wert zu gelangen.

Und hier einige Bemerkungen:

1. Die Liste muss absteigend sortiert werden.
2. Das Programm liest die Daten aus benannte Bereiche. Wenn die Liste erweitert wird, muss der benannte Bereich "Liste" angepasst werden.
3. Bei unglücklichen List- oder Suchwerten kann es sein, dass in der gewünschten Zeit keine Lösung gefunden wird. Dann kann man entweder die Sekunden erhöhen (wenn in der vorgegebenen Zeit schon relativ viele Kombinationen gefunden wurden) oder den Suchwert und die Abweichung anpassen (nicht ganz so genau).

[hrkplmstr]

Hallo,

WoW!!!

Vielen Vielen Dank.

Ich habe zwar keine Ahnung was du da gemacht hast, aber es funktioniert und ich kann diese Liste (falls ich darf) auch für andere Aufgaben solcher Art verwenden.

Könntest du mir vielleicht noch kurz erklären was du da gemacht hast?


Vielen Dank nochmals!

[Ego]

Hallo h...,

zu

Könntest du mir vielleicht noch kurz erklären was du da gemacht hast?

Deine Aufgabe wird in ähnlicher Form häufiger in Excel-Foren gestellt zB.

* zuschneiden von Leisten oder Rohren aus Stangen fester Länge
* stapeln von Leisten gleicher Breite auf vorgegebener Länge
* verteilen von zu sichernden Dateien auf Speichermedien vorgegebener Grösse
* verteilen von Geldstücken auf vorgegebener Beträge
...

Um eine optimale Verteilung zu bekommen könnte man (wenn man könnte) alle möglichen Kombinationen ausprobieren. Das würde aber mit deinen Daten, da es ca 10^26 mögliche Kombinationen gibt, auf meinem Rechner unter Excel mehr als 100 Milliarden Jahre dauern.
Da ich annehme, dass du nicht so lange warten wolltest habe ich einen Algorithmus überlegt, der in etwas kürzerer Zeit häufig ein einigermassen gutes Ergebnis liefert.
Deine Daten unterscheiden sich von den Daten in den obigen Anwendungen. Es sind fast alle Teile unterschiedlich gross und es gibt relativ viele relativ kleine Teile.
Der für diese Art von Teilen neu überlegte Algorithmus
1. nimmt im ersten Schritt die grössten Teile bis die Restgrösse kleiner als das dreifache des nächsten Teiles ist.
2. dann versucht er diese Restgrösse mit maximal 6 weitern Stücken möglichst vollständig und mit wenig Stücken aufzufüllen (nur noch weniger als 1 Milliarde Kombinationen).

zu

ich kann diese Liste (falls ich darf) auch für andere Aufgaben solcher Art verwenden

Natürlich.
Aber falls es in anderen Aufgaben viele Stücke mit gleicher Grösse und nicht soviele relativ kleine Stücke gibt, gibt es in den Foren vielleicht passendere Algorithmen.

Achtung die Hilfen in diesen Foren ist zwar kostenlos, aber nicht umsonst. Wenn du das Kleingedruckte vollständig gelesen hast, weist du, dass der Geholfene sich verpflichtet in anderen Situationen anderen auch kostenlose Hilfe zu geben. Schneeballsystem.