背包
背包 \(DP\)
今日 \(2025.10.23\)，距 \(CSP\) \(9\) 天，\(NOIP\) \(37\)天
昨天被線性 \(DP\) 爆切了，但確實學到一些巧妙的東西，然后就要開始今天的背包 \(DP\) 受虐學習了
今天的背包大部分都用了滾動數組優化空間，可能對初學者不太友好
01背包
luogu 板題 P2871 [USACO07DEC] Charm Bracelet S
#include<bits/stdc++.h>
using namespace std;
const int N=12885;
int n,m,a,b,f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a>>b;
for(int j=m;j>=a;j--){
f[j]=max(f[j],f[j-a]+b);
}
}
cout<<f[m];
return 0;
}
luogu P1048 [NOIP 2005 普及組] 采藥
#include<bits/stdc++.h>
using namespace std;
const int M=1005;
int n,m,f[M],a,b;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a>>b;
for(int j=m;j>=a;j--){
f[j]=max(f[j],f[j-a]+b);
}
}
cout<<f[m];
return 0;
}
luogu P1507 NASA的食物計劃
雙限制 \(01\) 背包，只需在枚舉狀態時多加一維限制即可，復雜度：\(O(n^3)\)
#include<bits/stdc++.h>
using namespace std;
const int M=404;
int n,H,T,h,t,w,f[M][M];
int main(){
cin>>H>>T>>n;
for(int i=1;i<=n;i++){
cin>>h>>t>>w;
for(int j=H;j>=h;j--){
for(int k=T;k>=t;k--){
f[j][k]=max(f[j][k],f[j-h][k-t]+w);
}
}
}
cout<<f[H][T];
return 0;
}
luogu P1855 榨取kkksc03
這是雙限制方案數 \(DP\)，本題可以把價值都當作 \(1\)，就和上一題一樣了
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,M,T,m,t,f[N][N];
int main(){
cin>>n>>M>>T;
for(int i=1;i<=n;i++){
cin>>m>>t;
for(int j=M;j>=m;j--){
for(int k=T;k>=t;k--){
f[j][k]=max(f[j][k],f[j-m][k-t]+1);
}
}
}
cout<<f[M][T];
return 0;
}
完全背包
要注意，完全背包是滾動數組優化的 \(DP\) 中最特殊的一種。\(01\)，分組，多重背包開滾動數組時，容量限制要 從大到小 遍歷，以此保證同一種物品 不會選多次，而完全背包不同，每種物品可選 無數次，所以可以由之前選過當前物品的狀態轉移過來，所以，容量限制要 從小到大（就算不開滾動數組，完全背包的容量也要從小到大遍歷）
P1616 板題 瘋狂的采藥
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,m,a;
long long f[N],b;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a>>b;
for(int j=a;j<=m;j++){
f[j]=max(f[j],f[j-a]+b);
}
}
cout<<f[m];
return 0;
}
分組背包
luogu 板題 P1757 通天之分組背包
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,a[N],b[N],c[N],f[N],cnt;
vector<int>v[N];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i]>>c[i];
cnt=max(cnt,c[i]);
v[c[i]].push_back(i);
}
for(int i=1;i<=cnt;i++){
for(int j=m;j;j--){
for(int k=0;k<v[i].size();k++){
int x=v[i][k];
if(j>=a[x]) f[j]=max(f[j],f[j-a[x]]+b[x]);
}
}
}
cout<<f[m];
return 0;
}
容量更新背包
對，我給它起名叫做這個，具體為什么看例題就理解原因了
luogu P1853 投資的最大效益
本題你會發現，每一年的總資產會增加，然后第二年的 背包容量 就更新成了這個 新的總資產，本題也是完全背包
階段：以每年為階段
狀態：\(f_{i}\) 表示花 \(i\) 元買股票所能獲得的最大利潤（注意，本題對于 \(100%\) 的數據有特殊性質，總資產和價錢都是 \(1000\) 的倍數，所以，為了節約空間，可以給總資產和價格都除以 \(1000\)，這樣不僅節省空間，也節約了時間）
轉移:和完全背包一模一樣
每個階段結束后，要更新容量（也就是題中的總資產），最后的答案也是總資產
#include<bits/stdc++.h>
using namespace std;
const int N=45,M=1e6+5;
int s,n,d,a[N],b[N],f[M],ans;
int main(){
cin>>s>>n>>d;
for(int i=1;i<=d;i++) cin>>a[i]>>b[i];
for(int i=1;i<=n;i++){
int m=s/1000;
for(int j=1;j<=d;j++){
for(int k=a[j]/1000;k<=m;k++){
f[k]=max(f[k],f[k-a[j]/1000]+b[j]);
}
}
s+=f[m];//更新總資產
}
cout<<s;
return 0;
}
luogu P5662 [CSP-J2019] 紀念品
本題和上題一模一樣，放到這里，供練習
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,v,f[10005],a[N][N];
int main(){
cin>>n>>m>>v;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<n;i++){
memset(f,0,sizeof(f));
for(int j=1;j<=m;j++){
for(int k=a[i][j];k<=v;k++){
f[k]=max(f[k],f[k-a[i][j]]+a[i+1][j]-a[i][j]);
}
}
v+=f[v];
}
cout<<v;
return 0;
}
紙幣三題
其實不能算是單獨一類一種背包，這所以列出一類，是為了說明 \(DP\) 中以不同標準作為階段的區別（三道題都是 完全背包 類的）
P2842 紙幣問題 1
本題是最優性問題，并且本題以 紙幣種類 或者 目標面額 為階段都可以
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=1e4+5;
int n,m,a[N],f[M];
int main(){
memset(f,0x3f,sizeof(f));
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
f[0]=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(i>=a[j]) f[i]=min(f[i],f[i-a[j]]+1);
}
}
cout<<f[m];
return 0;
}
P2840 紙幣問題 2
本題要求的是恰好湊出目標金額的紙幣 排列數
這就要注意了，排列是具有有序性的，例如，我有 \(1\)元、\(2\) 元的面額，要湊 \(3\) 元的面額，那么 \(1+2\) 和 \(2+1\) 算兩種方案
所以，階段就不能隨便定了，但我們可以確定的是，階段只可能是 組合出的面額 或者 紙幣種類，接著，分別假設
如果以 紙幣種類 作為階段，組合出的面額 作為狀態，不難發現，求出的方案中的紙幣是按紙幣編號排列的，也就是說，上面的例子就只能得到 \(1+2\) 一種方案，缺少了 \(2+1\) 的方案，所以這種不可取
那么，就以 組合出的面額 為階段，然后遍歷每種紙幣，不難發現，對于上面的例子，就可以湊出 \(1+2\) 和 \(2+1\) 兩種方案了，如果還不懂，就看代碼吧
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=1e4+5,mod=1e9+7;
int n,m,a[N],f[M];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
f[0]=1;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(i>=a[j]) f[i]=(f[i]+f[i-a[j]])%mod;
}
}
cout<<f[m];
return 0;
}
luogu P2834 紙幣問題 3
這道題要求組合數，然后不難發現，如果以紙幣種類為階段，求出的恰好就是組合數，和上一題的階段不同，求出的方案數代表的意義就不同（對于計數類 \(DP\) 是這樣的）
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=1e4+5,mod=1e9+7;
int n,m,a[N],f[M];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=a[i];j<=m;j++){
f[j]=(f[j]+f[j-a[i]])%mod;
}
}
cout<<f[m];
return 0;
}
好了，今天先到這里，筆者還得學校內的高考課。對了，還有一件事，在我的同學 \(hwh\) 的建議下，筆者準備寫寫自己平時獨立推出的數學方面的東西，可能會與高考課的內容有關，或者是筆者做某些題時引起的思考，或者是一些基礎的公式推導，個人感覺筆者的數學比 \(OI\) 好一些，好了，敬請期待吧！
浙公網安備 33010602011771號