Selecting Wine Dynamic Programming

Question

I have recently started learning Dynamic Programming and I have found the following question:

Imagine you have a collection of N wines placed next to each other on a shelf. For simplicity, let's number the wines from left to right as they are standing on the shelf with integers from 1 to N, respectively. The price of the i-th wine is pi (prices of different wines can be different).

Because the wines get better every year, supposing today is the year 1, on year y the price of the i-th wine will be y*pi, i.e. y-times the value that current year.

You want to sell all the wines you have, but you want to sell exactly one wine per year, starting on this year. One more constraint - on each year you are allowed to sell only either the leftmost or the rightmost wine on the shelf and you are not allowed to reorder the wines on the shelf (i.e. they must stay in the same order as they are in the beginning).

You want to find out, what is the maximum profit you can get, if you sell the wines in optimal order.

Source: 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

The answer goes over a top down approach and I wanted to create a bottom-up approach. Here is how I defined the problem:

F(l,r) is the profit function resulting from picking a wine from a specified left and right index

INPUT: p is an array of prices for the wines

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

constraint: l+r <= len(p)

I have created the following Python Code to tackle the issue

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

I have set the Price array to [2,3,5,1,4]. The source suggests that Max Profit is 50. However, I can't identify that value with the code I have written. Could someone assist in identifying the issue with my logic?

Answer 1

There are few points you'll have to take into consideration:

• In this approach, we have to work on diagonals and the lower half of the triangle will be zero
• Here year has to be maximum initially that is year = price.size().
• The current year would be calculated with formula (can choose any). I used this formula: year = year - (j-i) //This is useful for working on upper triangle
• You'll have to use DP array properly

int bottomUp(vector<int>price, int year, int start, int end) { int dp[100][100] = {0}; dp[start][start] = year*price[start]; for(int j=start+1; j<=end; j++) { for(int i=j; i>=0; i--) { int m = year-(j-i); int x = m*bottle[j] + dp[i][j-1]; int y = m*bottle[i] + dp[i+1][j]; dp[i][j] = max(x,y); } } return dp[start][end]; }

This code here returns the maximum value that is possible However, I am also pasting a screenshot of how the DP array will look

Answer 2

To fix the problem we need to iterate the array in a different order. Starting from the top-left corner we get following values by year:

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

and so every year we need to iterate a diagonal line instead of double loop over l and r. So, the code is:

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

Test run:

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