Auswahl Wein dynamische Programmierung

Question

ich vor kurzem begonnen habe, Dynamische Programmierung lernen, und ich habe folgende Frage gefunden:

Stellen Sie eine Sammlung von N Weinen gelegt nebeneinander auf einem Regal. Der Einfachheit halber nummerieren wir die Weine von links nach rechts, da sie auf dem Regal mit ganzen Zahlen von 1 bis N stehen. Der Preis des i-ten Weins ist pi (die Preise der verschiedenen Weine können unterschiedlich sein).

Da die Weine jedes Jahr besser werden, wenn heute das Jahr 1 ist, wird im Jahr y der Preis des i-ten Weins y * pi sein, also das y-fache des Werts des aktuellen Jahres.

Sie möchten alle Weine verkaufen, die Sie haben, aber Sie möchten ab diesem Jahr genau einen Wein pro Jahr verkaufen. Noch ein Zwang - jedes Jahr dürfen Sie nur den ganz links oder ganz rechts stehenden Wein im Regal verkaufen und Sie dürfen die Weine im Regal nicht nachbestellen (dh sie müssen in der Reihenfolge bleiben, in der sie am Anfang stehen).

Sie möchten herausfinden, wie hoch der maximale Gewinn ist, den Sie erzielen können, wenn Sie die Weine in optimaler Reihenfolge verkaufen.

Quelle: https://www.quora.com/Are-there-any-good-resources-or-tutorials-for-dynamic-programming-besides-the-TopCoder-tutorial/answer/Michal-Danil%C3%A1k?srid=3Otg

Die Antwort geht über einen Top-Ansatz, und ich wollte einen Bottom-up-Ansatz schaffen. Hier ist, wie ich das Problem definiert:

F (l, r) die Gewinnfunktion von resultierenden einen Wein aus einer bestimmten links Kommissionierung und rechten Zeige

INPUT: p ist eine Reihe von Preisen für die Weine

F (l, r) = max (Jahr * p [l] + F (l + 1, r) * (Jahr + 1), Jahr * p [r] + F (l, r- 1) * (Jahr + 1))

constraint: l + r < = len (p)

ich habe folgende Python-Code erstellt die Ausgabe

def wine(Price): 
    length = len(Price) 
    DP = [[0] * (length+1) for _ in range(length+1)] 

    for y in range(1,length+1): #Or can be range(length, 0, -1): 
     for l in range(0, length): 
      for r in range(length-1, -1, -1): 
       if l+r <= length: 
        DP[l][r] = max(y * Price[l] + DP[l+1][r] * (y+1), \ 
            y * Price[r] + DP[l][r-1] * (y+1)) 
    return DP 

ich den Preis Array auf [2,3,5,1,4] haben zu bewältigen. Die Quelle schlägt vor, dass Max Profit 50 ist. Jedoch kann ich diesen Wert nicht mit dem Code identifizieren, den ich geschrieben habe. Könnte jemand helfen, das Problem mit meiner Logik zu identifizieren?

Answer 1

Um das Problem zu beheben, müssen wir das Array in einer anderen Reihenfolge durchlaufen. Ausgehend von der linken oberen Ecke erhalten wir folgende Werte für Jahr:

# l is the vertical axis 
y0 y1 y2 y3 y4 
y1 y2 y3 y4 
y2 y3 y4 
y3 y4 
y4 

und so jedes Jahr brauchen wir eine diagonale Linie statt doppelter Schleife über l und r iterieren. So ist der Code:

def wine(price): 
    length = len(price) 
    DP = [[0] * (length+1) for _ in range(length+1)] # +1 for year0 in the corner 
    for y in range(1,length+1): # y1, y2... yN 
     for x in range(y+1): # intermediate values 0 to y 
      l = x # which is used to calculate the real l, r 
        # so, for the first year we get tuples (0, 1) and (1, 0) 
      r = y - l # we just go along the diagonal 
      # magic with l/r > 0 is used to prevent unwanted negative indexes 
      # so, False and price[-1] = False and max(False, 4) = 4 
      DP[l][r] = max(l > 0 and DP[l-1][r] + y * price[l-1], \ 
          r > 0 and DP[l][r-1] + y * price[-r]) 
    return DP 

Testlauf:

>>> pprint(wine([2,3,5,1,4])) 
[[0, 4, 6, 21, 33, 43], 
[2, 10, 13, 33, 48, 0], 
[8, 20, 25, 50, 0, 0], 
[23, 40, 50, 0, 0, 0], 
[27, 47, 0, 0, 0, 0], 
[47, 0, 0, 0, 0, 0]]