DP中的背包問題之中的無限背包問題
演算法筆記也有
當初我應該也是隨隨便便似懂非懂地就抓下來AC了
我個人認為他比一般背包問題好懂啦...
我們開一個陣列，長度為體積+1(包含0)，分別記錄當時體積能取得的最大價值
一開始當然預設為0囉
假設題目要的體積為10，三個物品的體積價值分別為
2,3 / 3,7 / 4, 1 / 1,1
我們就來實作吧
一開始的陣列狀況
0 0 0 0 0 0 0 0 0 0 0
代表0~10的最大價值都是0
接著我們把2,3放進去
當體積為0~1的時候，放不了(因為體積是2)，所以最大價值維持原樣
體積為2~3的時候能放1個，最大價值為3
...4~5為6...10為15
最後變成
0 0 3 3 6 6 9 9 12 12 15
然而注意到了嗎，3,6,9,12,15怎麼來的?
是可以從少2個體積的值那個值+3得來
處理完了2,3的最大價值
接著我們把3,7丟進去
當體積為0~2的時候，是放不下的，維持原樣
當體積為3時，我們有兩種選擇
1.維持原本陣列的值
2.更新陣列的值
原本的值是3，更新的值是0+7(體積0的最大值加上該物品價值)
我們要取最大值，因此被更新了
這樣持續下去更新體積4,5,6....10
會被更新成
0 0 3 7 7 10 14 14 17 21 21接著處理4,1
由於價值太小，會得到
0 0 3 7 7 10 14 14 17 21 21
處理1,1
在體積1的時候，更新的值(0+1)比原本的0大，更新
體積4的時候，也更新成5...
最後變成
0 1 3 7 8 10 14 15 17 21 22該陣列每個位置的值就代表那個體積可以存放的最大價值
體積0最多為0，體積1最多為1，體積2最多為3...
而假設題目要的是體積為10，也就是22
希望我打的這篇有人看得懂QQ