# 中電會五月主題課程
# 基礎動態規劃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)
{"title":"中電會五月主題課程–基礎動態規劃2","description":"點名","contributors":"[{\"id\":\"98ae9bd8-05ef-4e0a-b451-d465f67f398f\",\"add\":1030,\"del\":8}]"}