129 - 新鮮人的預算

jd3 · 發表於 2014-8-31 01:09:20

題意
有好幾個東西要買
有主件和附件之分
每個附件有對應的主件
要買附件時一定要買他的主件
預算有限，要如何買才能最滿族足
滿足度 = ( 各別物品價格*其滿意度 ) 的總和

(反白看提示)
提示1：DP
提示2：主件是0/1背包
提示3：附件是無限背包
提示4：DP表格只要開兩排(不然大概會MLE)

解法：需要DP、背包、滾動數組等概念才容易理解
提示的差不多了就直接進入解法價值實際上就是他給的價值*價格，怕版面混亂的話可以先算完
把主件和附件想成這樣一組一組的

像一般背包問題一樣一個個放進來
若先不考慮記憶體的問題
令 dp[ i ][ j ] = 在前 i 組裡用 j 元最大買到的滿足度
有個問題出現了，附件怎麼辦？
dp[ i ][ j ]並不一定有購買第 i 個

於是我們需要一組「有購買第 i 個主件」的情況，在這條陣列上面做附件的無限背包
所以另外開個dp2[n] 把dp[ i ][ 0~n ] 複製過去

在dp2上做無限背包前，別忘了要先購買主件 ( dp2[ j ] = dp2[ j - 主件價格 ] )
做完無限背包後更新 dp[ i ][ j ] = max( dp[ i ][ j ], dp2[ j ] )
於是dp[ i ][ j ]就達成目標了~

再來看記憶體問題
用到dp[ i ][ j ]時dp[ i -1 ]這排根本荒廢了
所以就重複使用dp[ 0 ][ n ]就AC囉~

我的CODE直接開了dp[ 2 ][ n ]
(算是偷懶吧)
CODE :

購買主題 已有 1 人購買 本主題需向作者支付 2 枚金幣 才能瀏覽

[TOJ] 129 - 新鮮人的預算

台南一中資訊社

程式設計達人 - 2014