Выбор вино динамического программирование

Question

Я недавно начал изучать динамическое программирование, и я нашел следующий вопрос:

Представьте, что вы едите коллекцию вин N, расположенные рядом друг с другом на полке. Для простоты, давайте укажем вин слева направо, поскольку они стоят на полке с целыми числами от 1 до N соответственно. Цена i-го вина - пи (цены на разные вина могут быть разными).

Поскольку вина становятся лучше с каждым годом, предположим, что сегодня это год 1, в год y цена i-го вина будет y * pi, то есть y-times значение, которое в текущем году.

Вы хотите продать все вина, которые у вас есть, но вы хотите продать ровно одно вино в год, начиная с этого года. Еще одно ограничение - каждый год вам разрешается продавать только крайнее левое или самое правое вино на полке, и вам не разрешается переупорядочивать вина на полке (т.е. они должны оставаться в том же порядке, что и в начале).

Вы хотите узнать, какая максимальная прибыль вы можете получить, если вы продаете вина в оптимальном порядке.

Источник: 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

Ответ переходит сверху вниз подход, и я хотел, чтобы создать подход снизу вверх. Вот как я определил проблему:

F (L, R) является функция прибыли в результате выбора вина из указанного левого и правого указателя

INPUT: р массив цен на (год + 1), год * p [r] + F (l, r) * (год + 1, r) * (год + 1), год * p [r] + F (l, r- 1) * (год + 1))

ограничение: L + R < = Len (р)

Я создал следующий код Python для решения проблемы

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 

Я установил массив цены на [2,3,5,1,4]. Источник предполагает, что Макс. Прибыль - 50. Однако я не могу идентифицировать это значение с кодом, который я написал. Может ли кто-нибудь помочь в выявлении проблемы с моей логикой?

Answer 1

Чтобы устранить проблему, нам нужно выполнить итерацию массива в другом порядке. Начиная с верхнего левого угла мы получаем следующие значения по годам:

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

и поэтому каждый год мы должны повторять диагональную линию вместо двойной петли над l и r. Таким образом, код:

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 

Пробное:

>>> 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]]