對于背包問題,經典的背包九講已經講的很明白了,本來就不打算寫這方面問題了。
但是吧。
我發現,那個最出名的九講竟然沒寫隊列優化的背包。。。。
那我必須寫一下咯嘿嘿,這么好的思想。
?
我們回顧一下背包問題吧。
?
01背包問題?
題目?
有N件物品和一個容量為V的背包。第i件物品的費用是c[i],價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量,且價值總和最大。?
這是最基礎的背包問題,特點是:每種物品僅有一件,可以選擇放或不放。?
f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是:
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。?
就是說,對于本物品,我們選擇拿或不拿
比如費用是3.
相關圖解:
我們求表格中黃色部分,只和兩個黑色部分有關
拿了,背包容量減少,我們價值加上減少后最大價值。
不拿,最大價值等于沒有這件物品,背包不變,的最大價值。
完全背包問題?
題目?
有N種物品和一個容量為V的背包,每種物品都有無限件可用。第i種物品的費用是c[i],價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量,且價值總和最大。?
基本思路?
這個問題非常類似于01背包問題,所不同的是每種物品有無限件。
f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}
圖解:
因為我們拿了本物品還可以繼續拿無限件,對于當前物品,無論之前拿沒拿,還可以繼續拿,所以是f[i][v-c[i]]+w[i]
?
換一個角度說明這個問題為什么可以f[i][v-c[i]]+w[i],也就是同一排。
其實是這樣的,我們對于黃色部分,也就是當前物品,有很多種選擇,可以拿一個,兩個。。。一直到背包容量不夠了。
也就是說,可以不拿,也就是J1,可以拿一個,也就是G1+w[i],也可以拿兩個,也就是D1+2w[i],拿三個,A1+3w[i]。
但是我們看G2,G2其實已經是之前的最大了:A1+2w[i],D1+w[i],G1他們中最大的,對么?
既然G2是他們中最大的。
我們怎么求J2?
是不是只要求G2+w[i]和J1的最大值就好了。
因為G2把剩下的情況都保存好了。
?
多重背包問題?(正文)
題目?
有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用,每件費用是c[i],價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量,且價值總和最大。?
?
和之前的完全背包不同,這次,每件物品有最多拿n[i]件的限制。
思路一:我們可以把物品全都看成01背包:比如第i件,我們把它拆成n[i]件一樣的單獨物品即可。
思路二:思路一時間復雜度太高。利用二進制思路:一個n位二進制,能表示2^n種狀態,如果這些狀態就是拿了多少物品,我們可以把每一位代表的數都拿出來,比如n[i]=16,我們把它拆成1,2,4,8,1,每一堆物品看成一個單獨物品。
為什么最后有個一?因為從0到16有十七種狀態,四位不足以表示。我們最后補上第五位1.
把拆出來的物品按01背包做即可。
思路三:我們可以利用單調隊列:
https://blog.csdn.net/hebtu666/article/details/82720880
再回想完全背包:為什么可以那么做?因為每件物品能拿無限件。所以可以。而多重背包因為有了最多拿多少的限制,我們就不敢直接從G2中拿數,因為G2可能是拿滿了本物品以后才達到的狀態?。
比如n[i]=2,如果G2的狀態是2w[i],拿了兩個2物品達到最大值,我們的J2就不能再拿本物品了。
如何解決這個問題?就是我給的網址中的,雙端單調隊列
利用窗口最大值的思想。
大家想想怎么實現再看下文。
?
發現問題了嗎?
我們求出J2以后,按原來的做法,是該求K2的,但是K2所需要的信息和J2完全不同,紅色才是K2可能需要的信息。
所以我們以物品重量為差,先把黑色系列推出來,再推紅色系列,依此類推。
這個例子就是推三次,每組各元素之間差3.
這樣就不會出現構造一堆單調隊列的尷尬情況了。
在代碼中繼續詳細解釋:
//輸入
int n;
int W;
int w[MAX_N];
int v[MAX_N];
int m[MAX_N];
?
int dp[MAX_N+1];//壓空間,本知識參考https://blog.csdn.net/hebtu666/article/details/79964233
int deq[MAX_N+1];//雙端隊列,保存下標
int deqv[MAX_N+1];//雙端隊列,保存值
隊列存的就是所有上一行能取到的范圍,比如對于J2,隊列里存的就是G1-w[i],D1-2w[i],A1-3w[i]等等合法情況。(為了操作方便都是j,利用差實現最終的運算)
他們之中最大的就是隊頭,加上最多存儲個數就好。
?
?
?
void solve()
{for(int i=0;i<n;i++)//參考過那個網址第二題應該懂{for(int a=0;a<w[i];a++)//把每個分組都打一遍{int s=0;//初始化雙端隊列頭尾int t=0;for(int j=0;j*w[i]+a<=W;j++)//每組第j個元素{int val=dp[j*w[i]+a]-j*v[i];while(s<t && deqv[t-1]<=val)//直到不改變單調性t--;deq[t]=j;deqv[t]=val;t++;//利用隊頭求出dpdp[j*w[i]+a]=deqv[s]+j*v[i];if(deq[s]==j-m[i])s++;//檢查過期}}}
}
?