背包问题专项
01背包问题
每种物品只能拿一个的问题称为01背包问题。
对于一维约束的情况，先正向枚举数量，再反向枚举约束条件。
核心代码：
1 | for(int i=1;i<=n;i++) |
上述代码中设n为数量，m为最大重量，v[i]为第i个物品重量，w[i]为第i个物品价值。
对于二维约束的情况，只需要改用二维数组，并再加一个for即可。
核心代码：
1 | for(int i=1;i<=n;i++) |
上述代码中设n为数量，m为最大重量，u为最大体积，v[i]为第i个物品重量，p[i]为第i个物品体积，w[i]为第i个物品价值。
对于更多维约束条件，可参照二维约束外推。
完全背包问题
每种物品可以拿无限个的问题称为完全背包问题。
对于一维约束的情况，先正向枚举数量，再正向枚举约束条件。（01背包是反向枚举约束条件）
核心代码：
1 | for(int i=1;i<=n;i++) |
上述代码中设n为数量，m为最大重量，v[i]为第i个物品重量，w[i]为第i个物品价值。
对于二维约束的情况，只需要改用二维数组，并再加一个for即可。
核心代码：
1 | for(int i=1;i<=n;i++) |
上述代码中设n为数量，m为最大重量，u为最大体积，v[i]为第i个物品重量，p[i]为第i个物品体积，w[i]为第i个物品价值。
对于更多维约束条件，可参照二维约束外推。
多重背包问题
01背包问题是每种物品只能拿一个，完全背包问题是每种物品可以拿无限个，而多重背包就是每种物品可以取一个或多个，但绝对是有限个，不可能无限取。
解决此类问题，只需把每种物品拆成单个即可。如第i种物品有j个，单个重量为v[i]，价值为w[i]，那就可以拆分成j的单个重量为v[i]，价值为w[i]的物品。
拆单之后，即可使用01背包问题的解法来解决。
混合三种背包问题
顾名思义，混合三种背包问题就是以上三种的混合。每种物品既可能只有1个，又可能有多个，还可能有无数个。
对于该类问题，先按多重背包问题的解法，将有多个的物品全部拆单，使得混合三种背包问题简化为01背包和完全背包的混合；再正向枚举每件物品，按每件物品所属性质不同而决定采用正向枚举约束条件还是反向。
核心代码：
1 | for(int i=1;i<=n;i++) |
上述代码中设n为数量，m为最大重量，v[i]为第i个物品重量，w[i]为第i个物品价值，f[i]=1表示第i个物品属于01背包，否则属于完全背包。
对于二维约束的情况，只需要改用二维数组，并再加一个for即可。
核心代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15for(int i=1;i<=n;i++)
if(f[i]==1)
{
for(int j=m;j>=v[i];j--)
for(int k=u;k>=p[i];k--)
if(!ans[j][k]||ans[j][k]>ans[j-v[i]][k-p[i]]+w[i])
ans[j][k]=ans[j-v[i]][k-p[i]]+w[i];
}
else
{
for(int j=v[i];j<=m;j++)
for(int k=p[i];k<=u;k++)
if(!ans[j][k]||ans[j][k]>ans[j-v[i]][k-p[i]]+w[i])
ans[j][k]=ans[j-v[i]][k-p[i]]+w[i];
}
上述代码中设n为数量，m为最大重量，u为最大体积，v[i]为第i个物品重量，p[i]为第i个物品体积，w[i]为第i个物品价值，f[i]=1表示第i个物品属于01背包，否则属于完全背包。
对于更多维约束条件，可参照二维约束外推。