Summierung bis zu Maximalsumme optimieren |
| 12.02.2013, 21:41 | dschanz | Auf diesen Beitrag antworten » | ||
| Summierung bis zu Maximalsumme optimieren Hallo an die Mathe-Profis! Ich suche eine Lösung für folgendes Problem: Gegeben sei eine Anzahl von Artikeln, deren Einzelpreise sich im Bereich bis maximal z. B. 1000 Euro bewegen. Die Preissumme aller Artikel soll mehrere Tausend Euro betragen, auf jeden Fall weit über 1000 Euro liegen. Jetzt sollen die Artikel zu Gruppen zusammengefasst werden, und zwar so, dass die Preissumme innerhalb jeder Gruppe 1000 Euro nicht überschreitet, aber maximal ist, und somit die Anzahl der gebildeten Gruppen sowie der verbleibende Rest so minimal wie möglich werden. Das Problem liegt also darin, besonders in Fällen stark gestreuter und somit unübersichtlicher Preisstückelung so wenig Gruppen wie möglich zu erzeugen. Also herauszufinden, ob es bei einer gegebenen Preisstückelung möglich ist, den Gesamtpreis von z. B. 3995 Euro in 4 Gruppen mit je einer Preissumme von max. 1000 Euro unterzukriegen, oder ob das mathematisch einfach nicht geht, weil die Stückelung der Preise ungünstig ist und man somit in jedem Fall 5 Gruppen bekommt. Angenommen, die 3995 Euro setzen sich aus 6 Artikeln zu je 350 Euro, 6 Artikeln zu je 300 Euro und einem zu 95 Euro zusammen, dann ist das noch recht überschaubar: 3 Gruppen zu je 1000 Euro (2 Artikel zu je 350 Euro + einer zu 300 Euro) 1 Gruppe zu 995 Euro (3 Artikel zu je 300 Euro + den einen zu 95 Euro) Also: 4 Gruppen sind möglich. Wenn sich die 3995 Euro aber aus 13 Artikeln zu je 300 Euro und einem zu 95 Euro zusammensetzen, geht nur das hier: 1 Gruppe zu 995 Euro (3 Artikel zu je 300 Euro + den einen zu 95 Euro) 3 Gruppen zu je 900 Euro (3 Artikel zu je 300 Euro) 1 Gruppe zu 300 Euro (der übrigbleibende 300-Euro-Artikel) Eine Lösung mit 4 Gruppen gibts da wohl nicht. Oder habe ich was übersehen? Aber wie löst man das Problem mathematisch exakt, also nicht durch Ausprobieren, besonders in nicht ganz so offensichtlichen Fällen? Gibt es für so was eine allgemein anwendbare Formel, mit der man möglicherweise auch mit Werten aus einer Datenbank auf einer Webseite (z. B. mit PHP) eine solche Optimierung anstellen kann? Da wäre ich für Tipps wirklich sehr dankbar! Gruß dschanz Meine Ideen: Außer, dass ich alle möglichen Kombinationen systematisch durchprobiere, fällt mir leider nichts dazu ein, aber das wäre bei entsprechend großer Zahl an Artikeln auch recht aufwendig. Außerdem bin ich mir nicht sicher, ob und wie ich dabei, besonders in Grenzfällen - z. B. sehr viele Artikel mit kleinen, unterschiedlichen Einzelpreisen und nur geringen Preisunterschieden - auch wirklich das Optimum finde. |
||||
| 13.02.2013, 19:32 | Abakus | Auf diesen Beitrag antworten » | ||
RE: Summierung bis zu Maximalsumme optimieren
Hallo, eine Formel dafür gibt es meines Wissens nicht, du kannst nur alle Möglichkeiten durchprobieren. Das Problem ist NP-vollständig auch. Allerdings gibt es sehr gute heuristische Verfahren, zB mit Genetischen Algorithmen, womit die Lösung oder eine gute Näherungslösung ermittelt werden kann. Abakus 
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
