Möglicher Algorithmus...?

18.11.2012, 12:30	Rumba	Auf diesen Beitrag antworten »
Möglicher Algorithmus...? Hallo zusammen, im Rahmen eines Projektes bin ich auf eine Problemstellung gestoßen, deren Lösung ich vermute zwar gefunden zu haben, allerdings habe ich Probleme Sie "handwerklich zu lösen" ... Ausgangssituation: Absteigend geordnete Liste mit Werten (z.B. Angabe der Fläche eines einzelnen Lagerplatzes in m²) sowie deren Gesamtsumme (z.B. Gesamt-Fläche eines Lagers). Problem: Die Gesamtsumme wird um einen bestimmten Betrag reduziert (z.B. die Gesamt-Fläche des Lagers um 10%). Vorgehen: Man möchte nicht alle Einzelwerte um 10% reduzieren, um in der Gesamtsumme 10% niedriger zu sein, sondern möglichst wenig Werte angehen und zwar die, die einen "großen Hebel" haben. Die Lösung/das Vorgehen soll wie folgt aussehen: $\begin{eqnarray} x_{n} \end{eqnarray}$ : Werte (z.B. Fläche) $\begin{eqnarray} n \in (1...g...n) \end{eqnarray}$ z.B. Gesamtfläche des Lagers 1000 m² $\begin{eqnarray} \sum\limits_{k=1}^n x_{k} = 1000 \end{eqnarray}$ , größte Einzelfläche $\begin{eqnarray} x_{1} = 100 m² \end{eqnarray}$ man will nun so lange diese Liste "durch gehen", bis Folgende Lösung gefunden wurden t: stellt das Ziel dar (in diesem Fall also 900m²; 10000,9) $\begin{eqnarray} t\geq \sum\limits_{k=g}^n x_{k} + (g-1)x_{g} \end{eqnarray}$ Das bedeutet, dass in der Liste nun alle Flächen oberhalb der "Grenzgröße" $\begin{eqnarray} x_{g} \end{eqnarray}$ auf diese verkleinert werden sollen. $\begin{eqnarray} x_{g} \end{eqnarray}$ ist somit die erste Fläche, die unverändert bleibt, alle kleineren ebenfalls. Nun ist die Frage wie ich $\begin{eqnarray} x_{g} \end{eqnarray}$ finde. Ich denke/vermute, dass dies nur mit einem Algorithmus möglich ist... Jemand eine Idee, wie es zu lösen ist? Für Anregungen zu Fehlern oder aber auch alternativen Lösungswegen bin ich natürlich auch sehr dankbar! Vielen Dank und noch einen schönen Sonntag! Beste Grüße Rumba
18.11.2012, 12:50	riwe	Auf diesen Beitrag antworten »
RE: Möglicher Algorithmus...? schau einmal unter rucksackproblem
18.11.2012, 14:25	Rumba	Auf diesen Beitrag antworten »
Hallo, vielen Dank für die schnelle Antwort, aber ich bin mir nicht sicher, ob es das richtige Vorgehen ist: Ziel ist ja nicht eine "optimale" Lösung zu finden, sondern einfach nur die "Top-Down" durchzugehen, bis das Problem gelöst ist... Vielen Dank erneut!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »