對象堆棧，動態編程

我正在處理一個類似於可以用動態編程算法解決的盒子堆疊問題的問題。我在這裏閱讀了關於它的帖子，但是我很難理解DP方法，並且希望對它的工作原理做一些解釋。下面是手頭的問題：對象堆棧，動態編程

鑑於X對象，每個都有自己的權重「W」和強度的「，你怎麼許多可堆疊在彼此的頂部？一個物體可以攜帶它自己的重量和其上的所有重量的總和，只要它不超過其強度。

據我所知，它有一個最佳的子結構，但它的重疊子問題部分讓我困惑。我試圖創建一個遞歸樹來查看它會多次計算相同的東西，但我無法弄清楚函數是否需要一個或兩個參數。

2016-12-28 ALEXANDER WORMBS

我認爲這個問題屬於http://cs.stackexchange.com/。 – user28434

你能指出這個問題的根源嗎（提供[適當的歸屬]（http://cs.stackexchange.com/help/referencing）來源）？你能鏈接到你指的SO帖子，並告訴我們你的具體困惑是什麼？另外，你有什麼嘗試？您可能想參考我們的[關於動態編程的參考資料]（http://stackoverflow.com/tags/dynamic-programming/info），然後告訴我們您取得了哪些進展。你嘗試過哪些子問題？ –

交叉發表：http://cs.stackexchange.com/q/68049/755，http://stackoverflow.com/q/41361652/781723。請[不要在多個網站上發佈相同的問題]（http://meta.stackexchange.com/q/64068）。每個社區都應該誠實地回答問題，不要浪費任何人的時間。 @ user28434，如果你要推薦另一個網站，請告知人們不要交叉發帖（否則會留下不好的經歷）。如果他們認爲在其他地方更合適，您可以建議他們刪除他們的問題並將其發佈到別處。 –

解決此問題的第一步是證明您可以找到具有從最高到最低強度排序的框的最佳堆棧。

然後，您只需按強度對盒子進行排序並找出哪些盒子包含在最佳堆棧中。

遞歸子問題有兩個參數：使用列表中的位置> = Y處的方框，找到堆放在堆棧頂部並使用X剩餘強度的最佳堆棧。

來源

2016-12-28 13:29:06

如果良好的DP解決方案存在，它需要2個PARAMS：

數
未訪問對象的總重量目前可以負擔得起（重量走訪對象不要緊訪問對象或未訪問的對象的數量）

爲了使它工作，你必須找到排序，在下一個對象的頂部放置對象是沒有用的。也就是說，對於任何違反此順序的解決方案，都有另一種解決方案遵循此順序並且更好或相等。

您必須證明選定的排序存在並明確定義它。我不認爲按照馬特蒂莫曼斯的建議通過力量進行簡單的排序就足夠了，因爲體重有一定的意義。但它的打樣部分...

來源

2016-12-28 13:37:37

對象堆棧，動態編程

回答

相關問題