Maximales Ergebnis ermitteln

[Daniel D.]

hi,

habe folgende daten in einem php-script vorliegen:

A B
318 4
636 8
762 9
954 12
1272 16
1524 18
1590 20
1908 24
2226 28
2286 29
2544 32
2862 36
3048 38
3180 40
3498 44
3810 47
3816 48
4134 52
4452 56
4572 58
4770 60
5088 64
5334 67
5406 69
5724 72

beliebige werte aus spalte A sollen addiert werden (kann auch ein wert mehrmals genommen werden) und gleichzeitig sollen die dazugehörigen werte aus der spalte B auch addiert werden.

allerdings darf die summe der werte aus spalte A nicht den wert 6000 überschreiten und das ergebnis der werte aus spalte B soll maximal hoch sein. wie kann man sowas mit php lösen?

mfg, daniel d.

[Encoder]

Klingt nach dem Rucksackproblem (engl. knapsack). Such mal danach, da wirst du zumindest nach einem Algorithmus fündig.

[borewa]

A B
318 4
636 8

[..]

5406 69
5724 72

denke das ist weniger ein PHP Problem, als ein Mathe problem.

Meine Idee wäre spontan ...

Wieviel A pro B
A

B

A B     A/B
318 4      79,5
636 8      79,5
[..]
5406 69     78,4
5724 72     79,5

Dann könnte man mit einer schleife immer den höchsten A/B Wert addieren, so lange es unter 6000 bleibt, bzw wenn es dadrüber kommt einfach den nächst kleiner A Wert nehmen so lange es mehrere gleich Starke A/B gibt.

Wobei dies auch nicht perfekt wäre, was nur diese mini Beispiel zeigt.
5724 könnte man nehmen, aber dafür die 318 nicht mehr addieren weil wir dann über 6000 sind. Somit hätten wir B mit 72.
Wenn wir aber nun 5406 nehmen, welche einen schlechteren A/B Wert hat und dann die 318 addieren bleiben wir unter den 6000 haben aber einen B Wert von 73, was ja um 1 besser ist.
Vielleicht einen Sonderfall beachten, wenn nur 1 A Wert genommen wird, das dann noch einer alternative gesucht wird. Aber trotzdem weiß ich nicht ob dann trotzdem die PERFEKTE lösung raus kommt, aber sie ist dem zumin nahe und sehr einfach umzusetzen.

Aber vielleicht hilft diese einfache Version trotzdem irgendwie bei deinem Problem, auch wenn sie nicht perfekt ist.

[Tom]

Hello,

habe folgende daten in einem php-script vorliegen:

A B
318 4
636 8
762 9
954 12
1272 16
1524 18
1590 20
1908 24
2226 28
2286 29
2544 32
2862 36
3048 38
3180 40
3498 44
3810 47
3816 48
4134 52
4452 56
4572 58
4770 60
5088 64
5334 67
5406 69
5724 72

beliebige werte aus spalte A sollen addiert werden (kann auch ein wert mehrmals genommen werden) und gleichzeitig sollen die dazugehörigen werte aus der spalte B auch addiert werden.

allerdings darf die summe der werte aus spalte A nicht den wert 6000 überschreiten und das ergebnis der werte aus spalte B soll maximal hoch sein. wie kann man sowas mit php lösen?

Es fehlen noch Bedingungen, bzw. ohne diese zusätzlicen Bedingungen kann man das realtiv einfach lösen. Du sagst, dass die Werte aus Spalte A mehrfach vorkommen dürfen. Da Du für Spalte B dazu nichts sagst, nehme ich an, dass das da auch gilt.

Wenn Die Summe der benutzten Werte aus B maximal werden soll bezüglich des Nichterreichens von 6000 Punkten in Spalte A, muss man nur herausfinden, welches Verhältnis von B/A den größten Wert ergibt.

Dieses Paar muss dann nr sooft aufaddiert werden (multipliziert werden), bis Die Summe_über(A)n gerade die vorgeschriebene Grenze nicht erreicht. Damit wird die Summe_über(B)n maximal in Bezug auf die Nebenbedingung.

Ich vermute aber, dass Du in deiner Aufgabenbeschreibung einfach noch eine Nebenbedingung vergessen hast.

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[Daniel D.]

hi,

Es fehlen noch Bedingungen, bzw. ohne diese zusätzlicen Bedingungen kann man das realtiv einfach lösen. Du sagst, dass die Werte aus Spalte A mehrfach vorkommen dürfen. Da Du für Spalte B dazu nichts sagst, nehme ich an, dass das da auch gilt.

Wenn Die Summe der benutzten Werte aus B maximal werden soll bezüglich des Nichterreichens von 6000 Punkten in Spalte A, muss man nur herausfinden, welches Verhältnis von B/A den größten Wert ergibt.

Dieses Paar muss dann nr sooft aufaddiert werden (multipliziert werden), bis Die Summe_über(A)n gerade die vorgeschriebene Grenze nicht erreicht. Damit wird die Summe_über(B)n maximal in Bezug auf die Nebenbedingung.

wenn aber gerade ein eintrag mit einem relativ hohen A-wert vorliegt (>3000), kann ich den nicht mehr multiplizieren und muß herausfinden, welche anderen A-werte da noch mit reinpassen. außerdem kann es auch sein, dass eher kleinere a-werte in summe den höchsten B-wert ergeben.

die von Encoder genannte sache mit dem rucksackproblem trifft es ganz gut, dahinter verbirgt sich letztendlich auch mein problem. mit dem mehrfachen vorkommen eines A-wertes ist letztendlich nicht notwendig, da die werte jeweils die vielfachen von (hier) 318 und 762 sind.

mfg, daniel d.

[Tom]

Hello,

die von Encoder genannte sache mit dem rucksackproblem trifft es ganz gut, dahinter verbirgt sich letztendlich auch mein problem. mit dem mehrfachen vorkommen eines A-wertes ist letztendlich nicht notwendig, da die werte jeweils die vielfachen von (hier) 318 und 762 sind.

Das sieht doch verflixt nach Payload von IP-Paketen aus...

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg