Max Gewinn einer Tabelle

[O2016]

Hallo,

ich soll den maximalen Gewinn beim Verkaufen eines Stückes aus einer Tabelle nehmen.
Komm aber irgendwie nicht so richtig drauf, dazu muss es rekursiv sein.

Gedanke:
Bsp: Tabelle

Ich habe Autos ( mir wurde eine Zahl übergeben bsp 8)
Anzahl [1,_2_,3_,4_,5_,6_,7,_8]
Preis__[ 1,5_,8,_9,_10,17,17,20]
(Ich habe _ und Platzhalter verwendet damit man sieht es gehört zusammen das obige zum unteren).
Also verkaufe ich 1 Auto bekomm ich 1 Preis, verkaufe ich 2 Autos bekomm ich 5 Preis... usw.

Man macht nicht mehr Gewinn wenn man Bsp 7 Autos auf einmal verkauft dann lieber 6 verkaufen und eines nochmal seperat, da man für beide sonst 17Preis bekommt.
zweites Beispiel: Ich habe 8 Autos. Kann ich in 4*2Anzahl verkaufen =4*5Preis=20
oder 1*8Anzahl=20Preis oder 1*6 Anzahl+1*2Anzahl=22Preis

Somit wäre 22 der beste Preis.

Hoffe ihr versteht die Logik.
Nun meine Überlegung.

// Teile die Autos durch die Anzahl. Geht es auf, nehme den Preis mal und merke das Ergebnis.
//Erhöhe um 1;
//Hier irgendwie Rekursion?!
//Geht es nicht auf teile das Auto durch die Anzahl. Merke dir die Zahl und nehme es mit dem Preis mal.(1)
//Merke dir den Rest und fange neu anzuzählen ... und das selbe nochmal
evtl hier auch rekursion?(2)
anschließend addiere (1)+(2) zusammen.

So ganz haut das nicht hin. Besteht die Möglichkeit, dass mir jemand so einen Text in NICHT-JAVA-TEXT REKURSIV schreibt, den ich dann umschreiben kann?

Wäre euch sehr dankbar.

 

[Tarrew]

So ganz verstehe ich deine Tabelle nicht.

Sind die Preise so fest vorgegeben? Es können also nur Zahlen zwischen 1 und 8 eingegeben werden?

 

[O2016]

Moment habe etwas vergessen. Wir haben eine Methode in der ich das alles schreiben muss und der wird
Autos und Preise übergeben. Tut mir leid.

Methodenname(int auto, long[] preise)

 

[Tarrew]

Dürft ihr das Preis-Array sortieren?

Wenn du das absteigend sortierst nach preis[index]/(index+1), dann wirds nämlich ziemlich einfach

 

[O2016]

Prinzipiell ist das Preisarray schon sortiert. Wie oben 1,5,8,9... aber ich komm trotzdem nicht dahinter.

 

[O2016]

Also Bsp die Zahl 5. ich hab 5 Autos also sollte ich die Autos so verkaufen, dass ich einmal 3 und einmal 2 Verkauf macht einen Preis von 13. nur wie gehe ich da rekursiv vor?

 

[Meniskusschaden]

Wenn du das absteigend sortierst nach preis[index]/(index+1), dann wirds nämlich ziemlich einfach

Wenn ich die Aufgabenstellung richtig verstanden habe, funktioniert greedy nicht. Beispiel:

Anzahl:      1  2  3
Preis:       1 20 27
Preis/Stk.:  1 10  9

Wenn man 3 Stück gemäß Sortierung verkaufen würde, bekäme man 21, optimal wären aber 27.

 

[Xyz1]

3 mal 9 ist aber 27 und nich 21....
Der falsche Ansatz macht auch eine Sortierung nicht besser.

 

[Meniskusschaden]

3 mal 9 ist aber 27 und nich 21....

Wer hat denn behauptet, 3 mal 9 sei 21? Bei absteigender Sortierung nach Stückpreis verkauft man erst 2 Stück zu je 10 und dann 1 Stück zu 1, also insgesamt ein Erlös von 21.

 

[O2016]

Genau es ist nich tso ,dass wie normal dass man bei 3 Verkauften auf einmal mehr gewinn macht als bei 1x2 +1*1 (Gibt kein Mengenrabatt oder ähnliches) somit glaube ich funktioniert das nicht.
Jemand noch Tipps?

 

[mihe7]

Such einfach rekursiv nach dem besten Ergebnis.

 

[MoxxiManagarm]

Aus meiner sicht ist es das klassische Rucksackproblem.

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

 

[O2016]

na gut ich teste es mal. Danke