Algorithmus gesucht: effizientes Einkaufen
-
Moin! Zunächst mal: zugegeben etwas schräges Beispiel, ist auch aus einer Partylaune entstanden, aber die Lösung ist doch irgendwie etwas verzwickt:
Nehmen wir an ich habe eine beliebige Anzahl n von Objekten mit jeweils genau zwei Eigenschaften, zum Beispiel 1. Preis, 2. ml Alkohol
Der User gibt nun ebenfals beides an, also vorhandenes Geld und gewüschte Menge Flüssigkeit und die Aufgabe des Algorithmus ist es nun, eine Art Einkaufsliste (beliebiger Länge) mit Objekten zusammenzustellen, deren Kombination möglichst genau die gewünschten Werte ergibt.
Einfachste Lösung wäre wohl eine Art Bruteforce, aber da auch die Menge unterschiedlicher Objekte in der Ausgabe n beträgt würde der Aufwand wohl ins unermessliche steigen. Mein zweiter Ansatz war eine Art Alkoholquotient (gibts diese Größe schon?), also die ml durch den Preis zu teilen und dann die Liste aufzufüllen indem man sich an Getränken mit ähnlichem Quotienten entlanghangelt (für eins mit höherem Quotienten muss eins mit equivalent niedrigerem gewählt werden usw.)
Also Anwendungsbeispiel:
Geld: 14,00€ Gewünschte Menge: 900ml
Output:
Kiste Bier: 8€, 480ml
Pulle Schnaps: 5€, 300ml
Tüte Billigsangria: 0.88€, 112.5ml
= 13,88€, 892.5mlEigentlich müsste es für diese Art Problem doch schon eine Lösung geben? Wäre dankbar wenn mir jemand zumindest einen Ansatz geben könnte, ist ja bald Wochenende
-
Was feiert ihr fuer Partys?
Wer rechnet denn da schon in ml^^ L ist da angebracht.
Soll der Algorithmus ne mischung bringen, oder wenns ne 1 l Falsche gibt und ein liter gefordert ist, diese 1 l Flasche nehmen und gut ist!?
-
Du kannst gerne mal nach Begriffen wie "Rucksack-Problem" oder "Backpack-Problem" suchen, da findest du sicher etwas geeignetes.
(Anmerkung: Das Problem ist NP-vollständig, also findest du die optimale Lösung wohl nur per Brute Force. Für eine Näherungslösung ist dein Ansatz mit dem maximalen Preis/Leistungs-Verhältnis afair schon recht gut.)
-
psycho7765 schrieb:
Mein zweiter Ansatz war eine Art Alkoholquotient (gibts diese Größe schon?), also die ml durch den Preis zu teilen und dann die Liste
wir hatten immer den "knallfaktor" bestimmt und danach eingekauft. ist alkoholmenge (in liter) durch preis (in dm). naja, mangels dm sollte man umdefinieren. und mit € sind dann die zahlen langsam zu klein. schlage vor alkoholmenge (in ml) durch preis (in ct). und alles über 1 ist akzeptebel.
0,6 Kiste Bier: 8€, 480ml
0,6 Pulle Schnaps: 5€, 300ml
1,2 Tüte Billigsangria: 0.88€, 112.5ml
0,96 Kist Öttinger: 5€, 480ml
1,01 Pulle Billigglühwein 0.89Eu, 90mlähnlich verfährt man mit filmen. der django-faktor ist sichtbar umgebrachte pro minute. django bringts auf über 1.
und mit den beiden ma´zahlen ausgestattet, kann man seine freizeit enorm optimieren.
-
hohesC schrieb:
Wer rechnet denn da schon in ml^^ L ist da angebracht.
mein autochen verbraucht 0,00000006 quadratmeter.
naja, vielleicht ist liter/100km kein soo schlechtes maß, damit die zahlen handlich bleiben.
-
volkard schrieb:
0,96 Kist Öttinger: 5€, 480ml
Das ist jawohl das ekligste Zeug was es gibt!!!
Taugt nur als Abflußreiniger!
Trinkt ihr das da unten echt?!?!?
-
Das Zeuch kann man saufen, wenn man sich vorher mit Starkbier/Jägermeister die Geschmacksinne ausgeballert hat. Bzw ist es einem nach ein paar Liter normalen, guten Bier eh egal, mit was man sich bis zum Ende zukippt.
-
Schonmal danke für die Antworten.
Was feiert ihr fuer Partys?
Wer rechnet denn da schon in ml^^ L ist da angebracht.
Soll der Algorithmus ne mischung bringen, oder wenns ne 1 l Falsche gibt und ein liter gefordert ist, diese 1 l Flasche nehmen und gut ist!?Die Einheit hatte praktische Gründe, das Programm wird fürs Palm OS und da finde ich die Fließkommabehandlung irgendwie komisch. Außerdem reicht mein Integer für 65,536 Liter reinen Alkohol und das sollte dann doch genug sein.
Die Literflasche soll durchaus genommen werden, wenn die Preisdifferenz geringer ist als bei Kombinationen anderer Flaschen, ansonsten z.B 2 500ml Flaschen gleicher Konzentration die aber zusammen näher am Preislimit liegen usw.
Hatte noch vor eine Art 'Abwechslungsfunktion' reinzubauen, also dass noch nicht gekaufte Getränke bevorzugt werden und nicht 25* Glühwein rauskommt, aber das ist erst mal nebensächlich.Du kannst gerne mal nach Begriffen wie "Rucksack-Problem" oder "Backpack-Problem" suchen, da findest du sicher etwas geeignetes.
Hab mir schon gedacht dass das Problem in der Informatik schon existiert. Thx jetzt weiß ich zumindest wonach ich suchen muss.
wir hatten immer den "knallfaktor" bestimmt und danach eingekauft.
Genau so ist mein Programm auch entstanden
Schade war wohl doch keine allzu einmalige Idee.
-
psycho7765 schrieb:
Du kannst gerne mal nach Begriffen wie "Rucksack-Problem" oder "Backpack-Problem" suchen, da findest du sicher etwas geeignetes.
Hab mir schon gedacht dass das Problem in der Informatik schon existiert. Thx jetzt weiß ich zumindest wonach ich suchen muss.
Du glaubst gar nicht, mit welchen Problemen sich die Informatiker so beschäftigen
(allerdings reden sie dann normalerweise nicht von hochprozentigem)
-
(Anmerkung: Das Problem ist NP-vollständig, [...])
Das Rucksackproblem ist nur dann nicht NP-vollständig, wenn man es ganzzahlig macht, oder? Hab ich das jetzt richtig in Erinnerung?
-
Ringding schrieb:
Das Rucksackproblem ist nur dann nicht NP-vollständig, wenn man es ganzzahlig macht, oder? Hab ich das jetzt richtig in Erinnerung?
hab in erinnerung, daß man es sogar nur rucksackproblem nennt, wenn nur ganzzahlige anzahlen vorkommen können. das andere ist dann eher lineare optimierung mit simplex-algorithmus oder so.
leider isses hier ganzzahlig.
also die werden uns nicht 0.4553 Tüten Billigsangria verkaufen.
-
volkard schrieb:
Ringding schrieb:
Das Rucksackproblem ist nur dann nicht NP-vollständig, wenn man es ganzzahlig macht, oder? Hab ich das jetzt richtig in Erinnerung?
hab in erinnerung, daß man es sogar nur rucksackproblem nennt, wenn nur ganzzahlige anzahlen vorkommen können. das andere ist dann eher lineare optimierung mit simplex-algorithmus oder so.
leider isses hier ganzzahlig.
also die werden uns nicht 0.4553 Tüten Billigsangria verkaufen.Ich meine beide heissen Rucksack Problem, und auch nur das eine ist NP-vollständig.
Das andere heißt fractional ...
Zumindest laut dem Guru (Cormen).Moment...
http://www.google.de/search?hl=de&q=cormen+knapsack+fractional&btnG=Google-Suche&meta=Also: Das nicht-fraktionale Rucksack-Problem wird auch 0-1-Rucksack-Problem genannt.
KK THX