3. Algorithmus gesucht: effizientes Einkaufen

Algorithmus gesucht: effizientes Einkaufen

  • C

    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.)

    0
  • V

    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.

    0
  • V

    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.

    0
  • S

    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?!?!? 😮

    0
  • L

    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.

    0
  • P

    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.

    0
  • C

    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)

    0
  • R

    (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?

    0
  • V

    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.

    0
  • S

    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

    0
Anmelden zum Antworten