总述：01背包，完全背包，多重背包，分组背包的基础模板以及优化方式，该篇主要是模板，后续会更新题目
首先说明一下他们之间的区别01背包每个物品只有一个，只有两种选择——选或不选，完全背包每种物品都有无限个，多重背包每种物品的个数有限制，分组背包物品分成若干组，每组最多选一件。
下面给出一句话总结只能选一次 → 01 背包（逆序），能选无限次 → 完全背包（正序），
能选有限次 → 多重背包（拆分/优化），一组里挑一个 → 分组背包
动态规划理解方式
状态表示与状态计算
核心要素：动态规划问题需要从两个角度考虑：
状态表示：确定问题的状态维度及其含义
状态计算：推导状态转移方程的计算方法
状态本质：每个状态实际上表示一个集合，需要用多维变量（如）来描述
优化原则：应先建立朴素的状态表示和计算方式，再进行等价变形优化（如一维数组优化）
集合与属性
集合视角：动态规划中的每个状态都对应一个特定集合
属性类型：集合的数值属性只有三种：
最大值（如背包问题中的最大价值）
最小值（如最小代价问题）
数量（如方案计数问题）
表示关系：状态变量存储的是对应集合的某种属性值
集合划分原则：动态规划的状态计算本质上是集合的划分，需要满足两个基本原则：
不重复：每个元素（选法）只能属于一个子集
不遗漏：所有元素都必须被划分到某个子集中
属性选择：集合划分后需要计算的是集合的某种属性（如最大值、数量等），具体取决于问题要求
特殊情况处理：求最大值时允许子集间有重复，但求方案数时必须严格不重复（这些主要是我上网课总结出来的，以后每道题的思路我也将严格遵守该方法）
01背包
题目
有 N 件物品和一个容量为 M 的背包。
第 i 件物品：体积 w_i，价值 v_i，只能选 1 次或不选。
求不超过背包容量的最大总价值。
输入
M N
w1 v1
w2 v2
…
wn vn
数据范围
1<= N,M <= 1000
核心思路
状态表示：集合f[i][j]表示从前i个物品里选总体积不超过j的最大价值
状态计算：此时有两种情况
1.当前物品体积大于背包容量此时只能从前i-1个物品中选，故转移方程为f[i][j]=f[i-1][j]
2.当前物品体积小于背包容量此时又面临两种选择——选或不选，若选因为物品只有一个则现有体积为j-v[i],后续只能从前i-1个物品中选，故f[i][j]=f[i-1][j-v[i]]+w[i],若不选则和前一种情况一样，此时应取两种情况的最大值，转移方程为f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])，因为两种情况都有f[i-1][j]故可先赋值
朴素做法
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int w[N],v[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
return 0;
}
优化
观察代码我们可以注意到当前层是由上一层推导出来的，因此我们可以把上一层拷贝到当前层，直接在当前层中计算不断更新覆盖当前层，由此类推我们就可以把矩阵压缩成一行，实现二维到一维的跨越。也就是滚动数组优化，空间复杂度从O(n*j)优化成了O(j),这里还需要注意的是遍历顺序，为保证每个物品只被添加一次，j应该倒着循环
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int v[N],w[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j–){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
2. 完全背包
题目
有 N 种物品和容量 M 背包。
每种物品无限个，体积 w_i，价值 v_i。
求最大价值。
输入
同上：
M N
v1 w1
…
数据范围
1 <= N,M <= 1000
核心思路
状态表示：集合f[i][j]表示从前i个物品里选总体积不超过j的最大价值
状态计算：按照第i个物品选择的个数进行分组（0个、1个、2个…k个),最大选择数：k值受限于物品体积v[i]和背包容量j，满足k*v[i]<=j, f[i][j]这么多种情况里的最大值
状态计算：f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])
朴素做法
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int w[N],v[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
for(int j=0;j<=m;j++){
for(int k=0;k*v[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}
}
}
cout<<f[n][m]<<endl;
return 0;
}
优化
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i]……f[i-1][j-k*v[i]]+k*w[i])
f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2*v[i]]+w[i]……f[i-1][j-k*v[i]]+(k-1)*w[i])
观察上面两个式子我们可以发现f[i][j-v[i]]和f[i][j]从第二项开始每一项只相差w[i],因此我们可以去掉一重循环 把f[i][j]写成 f[i][j]=max(f[i-1][j],f[i-1][j-v[i]+w[i]) 和01背包一样当前层是由上一层推导出来的,也可以采取滚动数组优化，不一样的是这个不需要逆序
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int w[N],v[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i];
for(int j=v[i];j<=m;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
3. 多重背包
题目
N 种物品，容量 M。
第 i 种：体积 w_i，价值 v_i，最多选 c_i 个。
求最大价值。
输入
M N
v1 w1 c1
v2 w2 c2
…
数据范围
N <= 100, M <= 1000, c_i <= 100
核心思路
状态表示：集合f[i][j]表示从前i个物品里选总体积不超过j的最大价值
状态计算：按照第i个物品选择的个数进行分组（0个、1个、2个…k个),最大选择数：k值受限于物品体积v[i]和背包容量j和物品个数s[i]，满足k*v[i]<=j&&k<=s[i]
状态计算：f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])
朴素做法
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int w[N],v[N],s[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>v[i]>>w[i]>>s[i];
for(int j=0;j<=m;j++){
for(int k=0;k*v[i]<=j&&k<=s[i];k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);}
}
}
cout<<f[n][m]<<endl;
return 0;
}
二进制优化
核心思路：
利用倍增思想将第 i 种物品（数量为 s_i）拆分为若干组，每组物品的体积和价值乘以拆分系数 1, 2^1, 2^2, …… 2^（k-1）, si – 2^k + 1，从而将多重背包问题转化为经典的01背包问题求解。
#include<iostream>
#include<algorithm>
using namespace std;
const int N=25000;//数组大小开到logs*n
int f[N];
int v[N],w[N];
int n,m;
int main(){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
int a,b,s;
cin>>a>>b>>s;
int k=1;
//二进制拆分
while(k<=s){
v[++cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
//剩余不足2^k
if(s){
v[++cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;
//01背包
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j–){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
return 0;
}
单调队列优化
核心思路
观察到f数组按类更新，可以把f[0……m]按体积的余数拆分成v类（建议自己用printf语句试一下）
f[j]是由前面不超过数量s的同类值递推得到，因此可以用单调队列来维护窗口最大值
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v,w,s;
int f[N],g[N];
int q[N];//储存下标
int main() {
cin>>n>>m;
for(int i=1; i<=n; i++) {
memcpy(g,f,sizeof f);//f备份到g以顺序更新f值
cin>>v>>w>>s;
//枚举所有余数
for(int j=0; j<v; j++) {
int hh=0,tt=-1;
for(int k=j; k<=m; k+=v) {
//判断队头是否要滑出
if(hh<=tt&&q[hh]<k-s*v) hh++;
//使用队头最大值更新f————窗口中的最大值加上还能放入物品的价值，窗口在g上滑动
if(hh<=tt) f[k]=max(g[k],g[q[hh]]+(k-q[hh])/v*w);
//当前值比队尾更有价值
while(hh<=tt&&g[k]>=g[q[tt]]+(k-q[tt])/v*w) tt–;
//下标入队便于队头出队
q[++tt]=k;
}
}
}
cout<<f[m]<<endl;
return 0;
}
4. 分组背包
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 v_{i,j}，价值是 w_{i,j}，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。
接下来有 N 组数据：
每组数据第一行有一个整数 S_i，表示第 i 个物品组的物品数量；
每组数据接下来有 S_i 行，每行有两个整数 v_{i,j}, w_{i,j}，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0 < N, V \\le 100
0 < S_i \\le 100
0 < v_{i,j}, w_{i,j} \\le 100
核心思路
划分方式：枚举第i组物品选哪个或不选
状态转移方程 f[i][j]=max(f[i-1][j],max(f[i-1][j-v[i][k]+w[i][k]))
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int w[N][N],v[N][N],s[N];
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j–){
for(int k=0;k<s[i];k++){
if(j>=v[i][k])
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[m]<<endl;
return 0;
}
