酒選擇動態編程

所以這是一個相當有名的實施DP的例子，但由於某些原因，我不能完全理解算法，並且我一直堅持它很長一段時間（準備計算奧林匹克）。問題如下酒選擇動態編程

想象一下，你有N個葡萄酒在架子上相鄰放置。爲了簡單起見，我們將葡萄酒從左至右編號爲，它們分別站在貨架上，整數分別爲1至N，。第i種葡萄酒的價格是pi（不同葡萄酒的價格可能不同）。

因爲葡萄酒每年都變得更好，假設今天是一年 1，在年份y的第i個葡萄酒的價格將Y * PI，即本年度值即Y型倍。

你想賣掉你所有的葡萄酒，但是你想從今年開始每年銷售一種葡萄酒。還有一個制約因素 - 每年您只能出售架子上最左邊的或最右邊的葡萄酒，而且您不能在架子上重新訂購葡萄酒（即它們必須保持與它們相同的順序）開始時爲）。

你要搞清楚，什麼是最大的利潤，你可以得到，如果你的最優順序

而且在C解決方案銷售的葡萄酒++給出（沒有與記憶化，但一個解決方案几乎不成問題對我的疑問）：

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]); 
}

主要困惑我已經是關係到我們using.As據我能理解MAX（）函數，遞歸利潤（）函數計算什麼是總如果我們在去年銷售葡萄酒1，那麼利潤是多少？如果我們在去年銷售了葡萄酒2，那麼可以說葡萄酒1的總利潤更高，如果它在晚些時候賣出，那麼我們實際上不應該保留葡萄酒1（因爲它會在以後爲我們帶來更多利潤）並出售葡萄酒2（因爲它會獲得比葡萄酒少的利潤1），還是有我沒有得到的東西？

來源

2017-10-29 Saumay Dudeja

「有一種解決方案，但這對我的疑問並不重要」，這個動態規劃是一種記憶;如果你忽略它只是一個非常低效的算法。 – Yakk

@Yakk OP本身沒有DP問題，但在如何獲得這個問題的遞歸公式。因此，他認爲記憶對他的具體問題無關緊要。 – fjardon

這個遞歸的解決方案是，只是檢查所有可能的scenerios並返回它的最大值。一些分析，2可能conidition選擇最右邊或最左邊的everystep你可以選擇它們，所以你的算法工作O（2^n）這真的很慢。 max（）在這裏只是選擇更大的一個真正特別的東西。而這個解決方案不是動態的，你可以使用Memoization：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]);

它也可以這樣寫。

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

來源

2017-10-29 08:11:14 FortunA

至於我能理解，遞歸利潤（）函數計算會產生什麼利潤總額，如果我們在去年銷售的葡萄酒1，如果我們賣的葡萄酒2什麼是利潤總額在過去的一年。因此，讓我們說葡萄酒1的總利潤更高，如果它在晚些時候賣出，那麼我們實際上不應該保留葡萄酒1（因爲它會爲我們帶來更多的利潤），並出售葡萄酒2（因爲它會獲取一個利潤不到酒1）

沒有它的完全錯誤的，它是一個遞歸算法是計算什麼發生，如果在1年或在一年酒「最後一個」賣酒1，想象u有10酒MAX（）將爲未來10年計算並回答問題

來源

2017-10-29 08:22:34

酒選擇動態編程

回答

相關問題