夜雨聆风背包问题是信奥赛的超高频考点，CSP-J/S几乎每年都考，省赛里至少有1道是背包变种题，很多同学总搞混01背包、完全背包、多重背包的区别，今天给大家整理了3种背包的优化模板+适用场景，直接背下来套用就行，省赛遇到直接AC！
1. 01背包（每件物品只能选1次）
适用场景：物品不可拆分，选或不选二选一
优化模板（空间优化到O(n)）
// n是物品数，m是背包容量，w[i]是重量，v[i]是价值
vector<int> dp(m+1, 0);
for(int i=1; i<=n; i++){
// 逆序遍历：避免重复选同一个物品
for(int j=m; j>=w[i]; j--){
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
// dp[m]就是最大价值
易错点：必须逆序遍历容量，否则会变成完全背包
2. 完全背包（每件物品可以选无限次）
适用场景：物品可以重复选，比如硬币找零问题
优化模板
vector<int> dp(m+1, 0);
for(int i=1; i<=n; i++){
// 顺序遍历：可以重复选同一个物品
for(int j=w[i]; j<=m; j++){
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
变种题型：求方案数、求最小物品数，只需要把max改成sum或者min就行
3. 多重背包（每件物品最多选k次）
适用场景：每个物品有数量限制，最多选k个
二进制优化模板（时间复杂度O(n*m log k)，省赛足够用）
vector<pair<int, int>> goods; // 拆分后的物品：重量、价值
for(int i=1; i<=n; i++){
int w = w[i], v = v[i], k = cnt[i]; // cnt[i]是第i件物品的最大数量
// 二进制拆分：把k拆成2^0,2^1,...余数
for(int j=1; j<=k; j<<=1){
goods.push_back({w*j, v*j});
k -= j;
}
if(k>0) goods.push_back({w*k, v*k});
}
// 拆分后当成01背包做
vector<int> dp(m+1, 0);
for(auto &g : goods){
int w = g.first, v = g.second;
for(int j=m; j>=w; j--){
dp[j] = max(dp[j], dp[j-w] + v);
}
}
优化技巧：如果数量很大，直接当成完全背包做就行，不用拆分
✅ 省赛真题示例
2025 CSP-J T4就是典型的多重背包变种题，用上面的二进制优化模板，直接套进去10分钟就能写出来，很多同学丢分就是因为没记住模板，自己写暴力解法超时了。
