【動態規劃】01揹包問題
今天小編閒的不行,就開啟洛谷,隨便一打卡就是大吉,還宜刷題。
正巧上午比賽時有一道揹包問題,於是小編默默開啟試煉場,瞅準了揹包問題( 別問我為什麼 ),正所謂自知者明,小編也知道自己很水(建議看 揹包九講 ),於是挑了三道題:
在寫之前總得知道什麼是揹包問題吧,揹包問題一般長這樣:
題目:有N件物品和一個容量為V的揹包。第i件物品的費用是w[i],價值是value[i]。求解將哪些物品裝入揹包可使價值總和最大。
那麼如何解這種題目呢,先定義一個數組f[i][j]為當一共有i件物品,揹包容量為j時的最大價值。然後就要找狀態轉移方程了,小編以前總認為狀態轉移方程難寫,但是隻要一項一項列出來就好了。對於每一個物品,無非就兩種可能:要麼選,要麼不選。那麼先看選,凡是總有回報和代價把,選了之後代價是什麼呢?想一想,是不是選了之後揹包剩餘容量就減少了;那麼回報呢?當然是價值增加了唄。但是不選就不一樣了,應為啥也沒幹,最大價值和之前一樣,不增不減。這不就出來了嘛,兩種情況如下:
- 選:f[i][j]=f[i-1][j-w[i]]+value[i];
- 不選:f[i][j]=f[i-1][j];
因為題目求的是最大價值,所以兩者中取大的就可以了,得到以下狀態轉移方程:
f[i][j]=max(f[i-1][j-w[i]]+value[i],f[i-1][j]);
有沒有發現什麼,我們用了二維陣列,雖然時間上已經難以優化,但是空間上還是可以優化成一維陣列的,只要同時去掉i的那一個維度就可以了,因為二維陣列有太多不需要一直記錄的,直接不斷更新一維陣列(滾動陣列的方式)就可以了,更改如下:
f[j]=max(f[j-w[i]]+value[i],f[j]);
具體怎麼實現,看幾道吧。
先看第一道:
這道題處於秒殺的行列,直接用剛才的方法,把錢數看成是容量,把重要程度*價格看成是價值就好了,直接寫就行,程式碼奉上:
1 #include<iostream> 2 using namespace std; 3 long long cost[30000],w[30000],f[30000],ans; 4 int main() 5 { 6long long n,m; 7cin>>n>>m; 8for(int i=1;i<=m;i++) 9cin>>cost[i]>>w[i]; 10for(int i=1;i<=m;i++) 11for(int j=n;j>=cost[i];j--) 12{ 13if(j>=w[i]) 14f[j]=max(f[j],f[j-cost[i]]+w[i]*cost[i]); 15} 16cout<<f[n]; 17return 0; 18 }
先來看一下采藥,比上面的還簡單:
把時間看成容量,就可以了,程式碼獻上:
1 #include<iostream> 2 using namespace std; 3 int t,m,w[1000],cost[1000],f[1000]; 4 int main() 5 { 6cin>>t>>m; 7for(int i=1;i<=m;i++) 8cin>>w[i]>>cost[i]; 9for(int i=1;i<=m;i++) 10for(int j=t;j>=w[i];j--) 11{ 12f[j]=max(f[j],f[j-w[i]]+cost[i]); 13} 14cout<<f[t]; 15 16return 0; 17 }
最後來看小A點菜:
這道題乍一看沒思路,還按照剛才的思路:要麼吃,要麼不吃,吃有什麼代價,什麼回報呢?錢變少了,方案數變多了唄;不吃呢?還是原來的方案數。這樣兩種情況就出來了:
f[j-cost[i]]; f[j]
【注意】情況有變,這一次就不那麼簡單了,因為選和不選是兩種不同的方案數,題目求的是一共的方案數,所以不是max,不是min,而是+。
歸根結底長這樣: f[j]=f[j]+f[j-cost[i]];
這樣程式碼就出來了,程式碼呈上:
1 #include<iostream> 2 using namespace std; 3 int n,m,cost[100000],f[10000]; 4 int main() 5 { 6cin>>n>>m; 7for(int i=1;i<=n;i++) 8cin>>cost[i]; 9f[0]=1; 10for(int i=1;i<=n;i++) 11for(int j=m;j>=cost[i];j--) 12f[j]=f[j]+f[j-cost[i]]; 13cout<<f[m]; 14return 0; 15 }