1315| 0
|
[TOJ] 129 - 新鮮人的預算 |
題意
有好幾個東西要買 有主件和附件之分 每個附件有對應的主件 要買附件時一定要買他的主件 預算有限,要如何買才能最滿族足 滿足度 = ( 各別物品價格*其滿意度 ) 的總和 (反白看提示) 提示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 枚金幣 才能瀏覽
| |
<這是個人簽名欄位>
|
|