Brauche einen Denkanstoß für ein PHP script

Brauche einen Denkanstoß für ein PHP script (22 Beiträge, 382 Mal gelesen)

Du bist nicht angemeldet. [ Login/Registrieren ]

Hallo!

Wie würdet ihr folgendes Problem am elegantesten lösen?

Ich habe ein Array mit beliebig vielen Items:

$array[0]['quality'] = 105
$array[0]['cost'] = 40

$array[1]['quality'] = 153
$array[1]['cost'] = 18

$array[2]['quality'] = 120
$array[2]['cost'] = 35
... usw ...

Weiters habe ich 2 Variablen:
$wallet
$max_items

Was ich nun brauche ist folgendes:

$max_items ist z.B. 6, das heißt dass man MAXIMAL 6 items haben kann aus dem Array, aber eben auch weniger.
$wallet ist z.B. 200. Das ist der verfügbare Betrag mit dem man items "kaufen" kann. Jedes item hat unterschiedliche Kosten ('cost').

Ich will für den verfügbaren Betrag in $wallet die best mögliche Qualität an X items kaufen (wobei X hier $max_items ist, also z.B. 6, aber auch weniger). Es kann also auch vorkommen dass (wieder bei $max_items 6) man sich 5 items leisten kann (z.B. einfach die 5 items mit der besten 'quality'), aber dass 4 items mit der besten 'quality' + 2 items mit geringerer 'quality' (und geringere 'cost') in Summe eine höhere 'quality' hat.

Ich hoffe ich habe mich verständlich ausgedrückt

Als Beispiel mit $max_items = 6 und $wallet = 200:

('quality'/'cost') ... (höhere 'quality' muss nicht zwingend höhere 'cost' heißen):

Item 1: 300/40
Item 2: 275/35
Item 3: 250/30
Item 4: 225/30
Item 5: 200/45
Item 6: 175/30
Item 7: 150/35
Item 8: 125/23
Item 9: 100/25

Wenn man jetzt einfach die items mit der besten 'quality' nehmen würde, käme man auf folgende Summe bei 'quality' und 'cost':
(Item 1 + Item 2 + Item 3 + Item 4 + Item5)
'quality': 300+275+250+225+200 = 1250
'cost': 40+35+30+30+45 = 180
Ein weiteres item würde sich nicht mehr ausgehen da schon 180 von 200 aus $wallet benutzt worden sind.

Wenn man aber auf Item 5 verzichtet und stattdessen Item 6 und Item 7 wählt kommt man in Summe auf eine höhere 'quality' und hat max_items = 6 auch nicht überschritten:
(Item 1 + Item 2 + Item 3 + Item 4 + Item 6 + Item 7)
'quality': 300+275+250+225+175+150 = 1375
'cost': 40+35+30+30+30+35 = 200

Habe mich schon mit dem Array herumgespielt (max, sum, sort, mit schleifen, etc.), aber so wirklich komm ich nicht dahinter wie das script alle Bedingungen berücksichtig

Das ist eine Variante des Rucksackproblems:

http://de.wikipedia.org/wiki/Rucksackproblem

Gewicht ist bei dir Cost und Nutzwert ist Quality.

Du müsstest aber noch die Items limitieren. Dazu hab auch auf die Schnelle das hier gefunden:

http://cs.stackexchange.com/questions/18492/variant-of-the-knapsack-problem

23.04.2014, 14:28 Uhr - Editiert von hellbringer, alte Version: hier

Danke!

Wenn du wüsstest wonach ich schon gegoogled habe ^^

Wenn man weiß wonach man suchen soll ist es gleich einfacher

*edit: Ah, bis Kombinatorik bin ich vorher schon gekommen, hab aber irgendwie keinen Zusammenhang mit meiner Aufgabenstellung gesehen ^^

23.04.2014, 14:33 Uhr - Editiert von hurt, alte Version: hier

Einer der Vorteile eines Informatikstudiums! Vorlesungstitel damals: Algorithmen und Datenstrukturen.

Mfg lukas

Einer der Vorteile eines Informatikstudiums!

Oder man lernt Google zu bedienen

Ohne das Wort Rucksackproblem kann man lange googeln. Das hat er selbst gemerkt.

Wenn wiki wieder geht, der Link auf die Bibel:
http://de.wikipedia.org/wiki/The_Art_of_Computer_Programming

Bei mir steckt derzeit die wikipedia, bei dir auch?

Mfg lukas

Ohne das Wort Rucksackproblem kann man lange googeln. Das hat er selbst
gemerkt.

Ich habs auch nur ergoogelt, ohne dem Wort Rucksackproblem.

Wenn wiki wieder geht, der Link auf die Bibel:
http://de.wikipedia.org/wiki/The_Art_of_Computer_Programming

Schaut interessant aus. Gibts das nicht als E-Book? Hab schon genug Totholz zuhause rumliegen.

Bei mir steckt derzeit die wikipedia, bei dir auch?

Hab hier keine Probleme damit.

Du musst verstehen, dass der Schöpfer von TeX besondere Ansprüche an ein ebook hat

http://www-cs-faculty.stanford.edu/~uno/news.html

Mfg lukas

Du musst verstehen, dass der Schöpfer von TeX besondere Ansprüche an ein ebook
hat

Von mir aus kauf ich ihm auch die TeX-Dateien ab und generier mir daraus selber die PDF

Wiki ist seit Tagen zeitweise sehr sehr langsam

Ok! Danke!

Mfg lukas

Ohne das Wort Rucksackproblem kann man lange googeln.

irgendwann stößt man auf das wort, wenn mans natürlich weiß oder gesagt bekommt, ist es noch einfacher.

Bei mir steckt derzeit die wikipedia, bei dir auch?

in den letzten tagen hab ich bemerkt, dass bilder extrem langsam oder nur halb laden. ein bildaufbau wie in den guten alten anfangstagen, schön streifenweise und nach 10sek sieht man dann das bild.

Ohne Hintergrundwissen WAS du suchen willst vergiss es.
Der Google Index beantwortet dir fast alles. Aber nur wenn du mit den richtigen Begriffen suchst, die du auch kennen musst.

Ohne Hintergrundwissen WAS du suchen willst vergiss es.
Der Google Index beantwortet dir fast alles. Aber nur wenn du mit den
richtigen Begriffen suchst, die du auch kennen musst.

Dass ich es gefunden habe, sollte doch eigentlich Beweis genug sein, oder?

Zufall

Zufall

Dann besteht wohl mein Arbeitsalltag aus einer Aneinanderreihung von Zufällen

wie nennt man zwei zufälle?

Schicksal?

oder möglicherweise besser in "wie füttere ich eine suchmaschine"?

Du müsstest aber noch die Items limitieren. Dazu hab auch auf die Schnelle das
hier
gefunden:http://cs.stackexchange.com/questions/18492/variant-of-the-knapsack-problem

Ist mit der 3rd dimension ein zusätzlicher Wert gmeint (siehe z.B. "Volumen": http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints ) auf den ich dann prüfen kann?

Also in die Richtung dass jedes item ein "Volumen" von 1 hat und dass maximal nur 6 Platz haben?

Dieses Forum ist eine frei zugängliche Diskussionsplattform.
Der Betreiber übernimmt keine Verantwortung für den Inhalt der Beiträge und behält sich das Recht vor, Beiträge mit rechtswidrigem oder anstößigem Inhalt zu löschen.
Datenschutzerklärung