如何用動態規劃解決這個揹包？

鑑於N對象，它們是1~n，第i個對象的體積是ti和ti <= M;同時，有很多盒子，每盒的容量是M。現在我們應該把所有這些對象放在的框中，1〜N的順序，盒子的最小數量應該用什麼？如何用動態規劃解決這個揹包？

例如，有5個物體，它們的體積爲{7,2,5,3,9}，順序爲1〜5。每個盒子的容量是10.所以最佳的解決方案是3盒子，它們分別是{7}，{2，5，3}，{9}。

我的解決方案：貪婪算法。假設第i個對象的最優解是x盒子被填充，剩餘空間是y，那麼對於i + 1對象，如果它的體積大於y，它必須被放入另一個新盒子。否則，一個選項是將它放入當前框中，並且解決方案是（x，y-v）;另一種選擇是把它放到另一個新盒子中，解決方案是（x + 1，M-v）。

問題：如何用動態規劃解決它？

2014-07-21 zangw

嘗試谷歌的裝箱問題計算的t_i總和。 –

@ user1990169謝謝 – zangw

這裏是我的問題的一個很好的例子，[http://amininima.wordpress.com/2013/08/01/dynamic-programming/](http://amininima.wordpress.com/2013/08/01 /動態編程/） – zangw

我不明白爲什麼你想它使用DP來解決，因爲你有一個完美的解決方案貪婪，但這裏是基於DP-想法：

讓F(k)是第一k對象的答案 - 我們可以將它們放入的最小數量的框。通過我們多少個對象放在最後一個方框讓我們的循環：

F(k) = min{F(l) + 1|l < k, t_(l+1) + t_(l+2) + .. + t_(k) <= M} 
F(0) = 0

複雜性是O(N*N)，如果我們在飛行中對每個k

2014-07-21 04:43:02 maksay

回答