🚀 go-pugleaf

Vielleicht noch als kleine Erg�nzung:
Martin hat nat�rlich recht, die L�sung muss nicht zwangsl�ufig "optimal"
sein. D.h., es muss nicht unbedingt die Rechnungskombination ausgew�hlt
werden, die einen m�glichst geringen Restbetrag hat. _Eine_
hundertprozentige L�sung gibt es nat�rlich immer. Man kann ja einfach ALLE
�berhaupt m�glichen Rechnungskombinationen �berpr�fen und daraus die beste
ausw�hlen. Wie Martin schon sagt, der Knackpunkt ist nat�rlich ob der
Aufwand vertretbar ist. Und hier explodiert der Aufwand mit der Menge der
Rechnungen. (n! - oder zumindest sowas �hnliches denk ich mal) Und da w�re
ein PC auch schon bei �berschaubarer Anzahl von Rechnungen schnell
�berfordert.

Nick



"Martin Fuchs" <mail@mafu-online.de> wrote in message
news:ak35je$1f7qc7$1@ID-134512.news.dfncis.de...
> > Sie haben eine Zahlung von einem Kunden, der bei Ihnen viele
> Rechnungen
> > unterschiedlicher H�he offenstehen hat.
> > Nun geht es darum, (die Zahlung ist < als die Gesamtsumme der
> Rechnungen)
> > festzustellen, welchen der x Rechnungen zusammen am n�hesten an den
> > Zahlbetrag kommen, am idealsten w�re nat�rlich das Ergebnis, welche
> dieser
> > vielen Rechnungen Zusammen gleich Zahlbetrag sind.
>
> Hallo Ines,
>
> Dein Problem ist eine Variante des sogenannten "Rucksack-Problems".
> Dieses ist f�r eine sehr grosse Anzahl von Rechnungen in der Praxis
> nicht berechenbar, d.h. es gibt f�r sehr grosse Anzahl von Rechnungen
> keinen Algorithmus, der mit vern�nftigem Aufwand (Zeitfaktor)
> _zwangsl�ufig_ das optimale Resultat liefert.
>
> Der L�sungsvorschlag, den Dir Nick angegeben hat, ist ein sogenannter
> Greedy-Algorithmus (gieriger Algorithmus). Sein Vorteil ist die
> geringe Komplexit�t (Aufwand), er liefert aber nicht zwangsl�ufig ein
> optimales Ergebnis, wie Du Dir an einfachen Beispielen leicht
> klarmachen kannst.
> Ggf l�sst er sich f�r Dein spezielles Problem noch verfeinern, ich
> denke z.B. daran, dass es eventuell mehrere Rechnungen mit dem
> gleichen Betrag gibt und der Zahlbetrag ein Vielfaches davon w�re.
>
> Gruss
>     Martin
>
>