Wine Selection Dynamische Programmierung

Question

Das ist also ein ziemlich berühmtes Beispiel für die Implementierung von DP, aber aus irgendeinem Grund kann ich den Algorithmus nicht vollständig verstehen, und ich bin seit einiger Zeit daran fest (Vorbereitung auf Computerolympiade) Problem ist wie folgt

Stellen Sie sich vor, Sie haben eine Sammlung von N Weinen nebeneinander auf ein Regal gelegt. Der Einfachheit halber nummerieren wir die Weine von links nach rechts als , sie stehen auf dem Regal mit ganzen Zahlen von 1 bis N, . Der Preis für den i-ten Wein ist pi (Preise für verschiedene Weine können unterschiedlich sein).

Da die Weine jedes Jahr besser, heute angenommen, ist das Jahr 1, auf Jahr y der Preis der i-ten Wein y * pi sein wird, das heißt y-fache der Wert, den laufenden Jahr.

Sie möchten alle Weine verkaufen, die Sie haben, aber Sie möchten ab diesem Jahr genau einen Wein pro Jahr verkaufen. Eine weitere Einschränkung - auf jedes Jahr dürfen Sie nur den am weitesten links oder den am weitesten rechts Wein im Regal verkaufen und Sie dürfen nicht die Weine im Regal bestellen (dh sie müssen in der gleichen Reihenfolge bleiben wie sie sind) am Anfang).

Sie wollen herausfinden, was der maximale Gewinn ist, können Sie erhalten, wenn Sie die Weine in optimaler Reihenfolge

und die Lösung in c verkaufen ++ gegeben (Es wurde eine Lösung mit memoization ist aber, dass kaum eine Rolle für meine Zweifel):

int p[N]; // read-only array of wine prices 


// year represents the current year (starts with 1) 
// [be, en] represents the interval of the unsold wines on the shelf 
int profit(int year, int be, int en) { 
    // there are no more wines on the shelf 
    if (be > en) 
    return 0; 
    // try to sell the leftmost or the rightmost wine, recursively calculate the 
    // answer and return the better one 
    return max(
    profit(year+1, be+1, en) + year * p[be], 
    profit(year+1, be, en-1) + year * p[en]); 
} 

die Haupt Verwirrung ich habe an die max() Funktion verwandt sind wir using.As soweit ich verstehen kann, die rekursive Gewinn() Funktion, was die Gesamt wäre berechnet Gewinn, wenn wir im letzten Jahr Wein 1 verkauften und was wäre der Gesamtpreis? wenn wir Wein 2 im letzten Jahr verkauft haben. So lässt sich sagen, dass Wein 1 den größeren Gesamtgewinn hat, wenn er in den späteren Jahren verkauft wird, sollten wir Wein 1 nicht behalten (weil er uns später mehr Gewinn bringt)) und verkaufe Wein 2 (wie es einen Gewinn weniger als Wein 1) holen würde, oder gibt es etwas, das ich nicht bekomme?

Answer 1

Diese rekursive Lösung ist, dass Sie einfach alle möglichen Szenarien überprüfen und Max zurückgeben. Einige Analyse, 2 mögliche Conidition wählen am weitesten rechts oder am weitesten links Sie können wählen, von ihnen so Ihr Algorithmus funktioniert O (2^n), die wirklich langsam ist. Max() ist hier, um nur etwas Größeres auszuwählen. Und diese Lösung ist nicht dynamisch, können Sie Memoization verwenden: https://en.wikipedia.org/wiki/Memoization.

return max( 
profit(year+1, be+1, en) + year * p[be], 
profit(year+1, be, en-1) + year * p[en]); 

könnte es auch so geschrieben werden.

int max_from_left = profit(year+1, be+1, en) + year * p[be] 

int max_from_right = profit(year+1, be, en-1) + year * p[en]); 

if(max_from_left > max_from_right) 
    return max_from_left 
else 
    return max_from_right 

Answer 2

Soweit ich verstehen kann, die rekursive Gewinn() berechnet, was den Gesamtgewinn wäre, wenn wir Wein 1 im letzten Jahr verkauft und was wäre der gesamte Gewinn, wenn wir Wein verkauft 2 im letzten Jahr.Also sagen wir, Wein 1 hat den größeren Gesamtgewinn, wenn er in den späteren Jahren verkauft wird, also sollten wir nicht tatsächlich Wein 1 behalten (weil er uns später mehr Gewinn bringen wird) und Wein 2 verkaufen (wie er a Gewinn weniger als Wein 1)

nicht sein völlig falsch, es ist ein rekursiven Algorithmus es berechnen, was passiert, wenn Verkauf Wein 1 im Jahr 1 oder Wein „letzten“ im ersten Jahr, vorstellt, u 10 Wein max hat() wird für die nächsten 10 Jahre berechnen und Antwort zurückgeben