# 背包問題 ## Knapsack ---- ### [題目敘述](https://atcoder.jp/contests/dp/tasks/dp_d) 現在有 $N$ 個物品， 第 $i$ 個物品的重量為 $w_i$、價值為 $v_i$， 你有一個容量為 $W$ 的背包， 求背包內物品的最大價值總和 > $N<=100$ , > $w_i<=W<=10^5$ , > $v_i<=10^9$ ---- ### 想一想 ---- #### 假設最後所選物品總重為 $x$ ， $x$ 會有幾種可能？ ---- 每種物品可以取或不取，是 $2^n$ 種嗎 ? 其實只有 $W$ 種，想想看為什麼 ---- #### 假設目前已經選了重量為 $y$ 的物品， #### 再選一個重量會變為多少？ ---- 可能變為 $y+w_1$ 、 $y+w_2$ 、 $y+w_3$ $\ldots$ $y+w_n$ 換句話說，一個重量為 $p$ 的狀態， 只能從 $p-w_1$ 、 $p-w_2$ 、 $p-w_3$ $\ldots$ $p-w_n$ 等狀態中轉移過來 ---- ### 狀態怎麼訂？ 如同之前所說的，狀態通常 $=$ 所求的答案， 於是乎，我們可以把 $dp[i]$ 定為， 所選物品重量總和為 $i$ 時的最大價值 ---- ### 怎麼轉？ $dp[0]=0$ $dp[i]=max(dp[i-w_k]+v_k)$ ( $1<=k<=n$ , $w_k<=i$ ) ---- ### 非~常重要的實作 ```cpp= const int N=105,MaxW=100005; int v[N],w[N]; int dp[MaxW]; void Knapsack(int n,int W){ for(int i=1;i<=n;i++){ // 遍歷每個物品 for(int j=W;j>0;j--){ // 從大到小遍歷重量 if(j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } } ``` #### 這段code有兩個重點 1. 遍歷重量是從大到小 2. 遍歷物品的迴圈在外 ---- ### 如果重量的迴圈是從小到大會怎麼樣 假設有個物品的重量是 $1$ ， 且價值是所有物品中最大的， 如果 $W>1$ 這個物品就會被取到兩次 ---- ### 如果遍歷重量的迴圈在外會怎麼樣 ---- ### 自己想 ~ --- ## 背包問題們 ---- ### 常見的背包問題可以分為三種 1. 01背包 2. 無限背包 3. 有限背包 --- ### [01背包](https://atcoder.jp/contests/dp/tasks/dp_e) #### 每個物品只有一個，可以選擇取或不取 ---- #### 剛剛給的例題就是01背包 （忘記的...自己[看著辦](https://atcoder.jp/contests/dp/tasks/dp_d) --- ### [無限背包](https://cses.fi/problemset/task/1633) 每個東西可以取無限次 ---- ### 怎麼做 感覺很複雜，其實只需稍微修改01背包的扣 ---- ### 想法 對於每個重量，最後一個選的， 可以是任何物品 ---- ### 程式～ ```cpp= const int N=105,MaxW=100005; int v[N],w[N]; int dp[MaxW]; void Knapsack(int n,int W){ for(int i=1;i<=W;i++){ // 從小到大遍歷重量 for(int j=1;j<=n;j++){ // 遍歷每個物品 if(i>=w[j]) dp[i]=max(dp[i],dp[i-w[j]]+v[j]); } } } ``` --- ### [有限背包](https://www.luogu.com.cn/problem/P1776) 每個物品不一定只有一個， 可以當成有重複物品的01背包 ---- #### 實作的部分 ```cpp= const int N=105,MaxW=100005; int v[N],w[N],num[N]; // num是每個物品的數量 int dp[MaxW]; void Knapsack(int n,int W){ for(int i=1;i<=n;i++){ // 遍歷每個物品 for(int k=0;k<num[i];k++){ // 每個物品可以取num[i]次 for(int j=W;j>0;j--){ // 從大到小遍歷重量 if(j>=w[i]) dp[j]=max(dp[j],dp[j-w[i]]+v[i]); } } } } ``` ---- ### 神奇的優化 ---- 先說，接下來的內容看不懂是完全正常的 ---- ### 複雜度分析 原本的做法，複雜度為 $O(N\times W\times num)$ ---- ### 優化想法 真的有必要分成 $num$ 個物品嗎？ 只要可以湊出 $1$ ～ $num$ 的這些數量就可以了吧 e.g. { $1,2,3$ } 就可以湊出 $6$ 以下的所有數字 ---- ### 那麼，要如何分塊呢？ ---- ### 二進位！ 假設物品總數為 $x$ ， 將 $x$ 分為 { $2^1$ , $2^2$ , $2^3$ , $2^4$ , $2^p$ , $q$ } $p$ 為使 $2^{p+1}-1<=x$ 的最大整數 $q=x-(2^{p+1}-1)$ ---- ### 醬一定可以嗎 假設有一個數量 $y$ 1. 如果 $y<2^{p+1}$ ，就可以用那些 $2^k$ 的湊出來 2. 不然的話先扣掉 $q$ ，就會變成 1. 的情況了 ---- ### 再來看看複雜度 塊數由 $num$ 塊，變成最多 $\log_2(num)+1$ 複雜度降為 $O(NW*log(num))$ ---- [Sample Code](https://cses.fi/paste/580181f237cc6f6f276335/) ---- ### 以下內容由PixelCat贊助播出 ---- ### PixelCat: 你有打算講 $O(NW)$ 的有限背包嗎 ---- ### 哪泥！？？！ 竟然可以 $O(NW)$ ---- ### 觀察一下 為了方便觀察，我們重新寫一個轉移式 $dp[i][j]=$ 目前用了前 $i$ 種物品 ， 重量為 $j$ 的最大價值 $dp[i][j]=max${ $dp[i-1][j-w[i]*k]$ } $+v[i]$ { $0<=k<=num[i]$ } ---- 可以發現，對於每個 $j$ 只會取到與他差 $w[i]*k$ 的重量 假設他取的重量為 $x$ 則有 $x\equiv j\pmod{w[i]}$ （這是同餘符號） ---- 換句話說 ### 我們只需要管同餘的那些重量 ---- 於是我們將同餘的數分在同一組 每次取出連續 $num[i]$ 格中最大值 可以維護一個[單調隊列](https://hackmd.io/@Paul-Liao/HkyhtXpAd#/) ---- [Sample Code](https://cses.fi/paste/feb80b9d9f7c56e22762ba/) --- ## 內容有點多 ## 請大家小心食用