背包 \(DP\)
今日 \(2025.10.23\)，距 \(CSP\) \(8\) 天，\(NOIP\) \(36\)天
昨天被线性 \(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\) 好一些，好了，敬请期待吧！