Skip to main content
 首页 » 编程设计

python之选择 Wine 动态规划

2025年02月15日12jirigala

我最近开始学习动态规划,我发现了以下问题:

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.

来源: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) 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)

我创建了以下 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]。消息来源表明 Max Profit 是 50。但是,我无法用我编写的代码识别该值。有人可以根据我的逻辑协助确定问题吗?

请您参考如下方法:

您必须考虑以下几点:

  • > 在这种方法中,我们必须处理对角线和下半部分 三角形将为零
  • 此处年份最初必须是最大值,即 year = price.size()。
  • 当前年份将使用公式计算(可以选择任何)。我用这个 公式:year = year - (j-i)//这对处理上三角很有用
  • 你必须正确使用 DP 阵列
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]; }

此处的代码返回可能的最大值 但是,我还粘贴了 DP 阵列外观的屏幕截图