# 中電會五月主題課程 # 基礎動態規劃2 --- 點名 回饋表單 --- ## [Book Shop](https://cses.fi/problemset/task/1158) ---- 經典的0/1背包問題 有$n$本書，第$i$本書有$s_i$頁，售價$h_i$元。你有$x$元，最多可以買到幾頁? * $1\leq n\leq 1000$ * $1\leq s_i,h_i, \leq 1000$ ---- 定義$dp[i][j]$為在前$i$本書中，花費$j$元最多可買到的頁數 ---- 則有兩種可能 沒買第$i$本書: $$ dp[i][j]=dp[i-1][j] $$ 有買第$i$本書: $$ dp[i][j]=dp[i-1][j-h[i]]+s[i] $$ ---- ```cpp= for(int j=h[0];j<=x;j++){ //因為i=0時沒有i-1，所以需要特別處理 //或把dp表格變成1-base dp[0][j]=s[0]; } for(int i=1;i<n;i++){ for(int j=0;j<=x;j++){ dp[i][j]=dp[i-1][j]; if(j>=h[i]){ dp[i][j]=max(dp[i][j],dp[i-1][j-h[i]]+s[i]); } } } ``` ---- ### 滾動優化 把表格畫出來後會發現 每一排(i=a)的答案都是由上一排(i=a-1)算出來的 所以可以只留最後兩排就好 ---- 實作上可以開兩個陣列 一個存現在的(A)，一個存上一排的(B) 每次由B算出A 然後把A放到B的位置 重複$n$次 可將空間複雜度從$\text{O}(nx)$降到$\text{O}(n)$ ---- 其實也可以只用一個陣列 ```cpp= for(int i=0;i<n;i++){ for(int j=x;j>=h[i];j--){ dp[j]=max(dp[j],dp[j-h[i]]+s[i]); } } ``` --- ## [CSES Dynamic Programming 題解](https://hackmd.io/@tmting39/H1yvegOYn)