背包模型
本质
从一堆物品中选，选择一些物品，使得这个选择满足某种条件，求最大值/最小值/方法数。
几种初始化
在设基本状态的时候有三种设法：
1.体积最多为j（一般的背包问题）
初始化所有值都是0，当体积的状态大于等于0的时候才能转换
2.体积恰好为j
初始化f[0]=0,其他的都是正无穷（根据题意设），当体积恰好是要求的体积且大于0的时候才能转换
3.体积最少为j（潜水员）
初始化f[0]=0，其他都是正无穷（根据题意） 当状态的体积小于0的时候也可以转换
01背包
容量为v的背包里，有n件物品，每件物品的体积为vi，价值为wi，求不超过背包体积的情况下能获得的物品的最大价值
有序变无序：从1~i依次遍历，那么处理到i的是吧前i-1个已经被处理过了，可以直接拿着算
f[i][j]表示在前i个物品中选，总体积不超过j的方案的能获得的最大价值
对于每个物品i，可以选和不选
不选：在前i-1个物品中选，体积不超过j的方案的最大价值
选：在前i-1个物品中选，体积不超过j-vi的方案的最大价值+wi
f[i][j]=max(f[i-1][j],f[i-1][j-vi]+wi);
可以优化成一维的数组：f[j]表示体积不超过j的方案的最大价值
因为每一次更新只和上一层有关
如果我们按顺序遍历的话，那么我们到j更新的时候所找到的j-vi已经在第i层更新过了，也就是说i已经被拿了，如果我们再按照这个更新的话会再拿一次i
那么我们i从第一个物品开始遍历，每次j从大到小更新:f[j]=max(f[j],f[j-vi]+wi)
这样的话当我们更新到j的时候，所用到的j-vi实际上是没有更新过的上一层i-1的最大价值，这样就避免了重复取值
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]);
}
}
01背包求方案数
原题链接：https://www.acwing.com/problem/content/280/
题意：
有n个数a[1],a[2]...a[n]，从他们中选出若干数使得和为m，那么有多少个方案。
思路：
f[i][j]表示在前i个物品中选，选出的数的和为j的方案数。
那么对于这个状态的方案数有两两部分组成：选i的方案数和不选i的方案数。
那么f[i][j]=f[i-1][j]+f[i-1][j-a[i]]
优化成一维，因为都是i-1层的所以j从大到小列举，注意f[j]已经是上一层的方案数，即f[i][j]已经等于f[i-1][j]了所以我们只用加上f[j-a[i]]就可以了。
#include<bits/stdc++.h>
using namespace std;
int n,m,p;
int f[10005];
int a[105];
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=m;j>=a[i];j--){
f[j]+=f[j-a[i]];
}
}
cout<<f[m]<<endl;
return 0;
}
完全背包
有一个价值为v的背包，n种物品，每种物品的数量都是无穷的，第i种物品的价值是wi，体积是vi，求不超过背包体积能获得的最大价值 f[i][j]表示在前i种物品中选，所选的物体总体积不超过j的最大价值
因为每种物品的数量是无限的，对于第i种物品可以选一个或者多个，所以转换的时候f[i][j]考虑的就是在前i种物品中选择，体积不超过j的最大价值，对于每种物品有两种情况：选或不选
选：f[i][j]=max(f[i][j],f[i][j]+wi)意为可以选择的物品可以在前i种里面挑
不选：f[i][j]=max(f[i][j],f[i-1][j])
j直接从小到大枚举就可以，优化之后是从v[i]开始枚举 （与01的区别就是j反向遍历）
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
如果要求背包装满，即恰好等于m，那我们设的状态是：f[i][j]表示在前i个物品里恰好选择了体积为j的物品获得的最大价值，那么我们初始化的时候f[i][0]表示在前i个物品选体积恰好为0的最大价值，那么是0，但是其他的状态下体积恰好是j的最大价值无解，那么我们就初始化所有情况为-INF，将f[i][0]设为0，然后我们再正常按01和完全背包做，当最后f[m]是-INF的话说明没有能正好装满的方案，如果不是-INF那就是最大价值
for(int i=1;i<=m;i++)f[i]=-INF;
f[0]=0;
完全背包求方案数
和01背包的思路一样，方案数等于不选的方案数加选的方案数
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=v[i];j<=m;j++){
f[j]+=f[j-a[i]];
}
}
cout<<f[m]<<endl;
多重背包
二进制优化
数据范围：n<=1000 v<=2000 si<=2000
有一个体积为v的背包，n种物品，每个物品的体积是vi，价值是wi，个数是si，求拿的物品的体积不超过背包体积时的最大价值
用二进制优化
对于一种背包，我们可以拿0 ~ si个，我们把他分成1,2,4...这种二进制个捆在一起作为一组，那么我们可以用这几组凑出0 ~ si中所有的数，然后对这几组进行01背包问题的拿取就可以了
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int f[N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int k=1;k<=s;k*=2){//将si个分成二进制个背包
for(int j=m;j>=k*v;j--){//然后对每个背包讨论选还是不选
f[j]=max(f[j],f[j-k*v]+k*w);
}
s-=k;
}
if(s>0){
for(int j=m;j>=s*v;j--){
f[j]=max(f[j],f[j-s*v]+s*w);
}
}
}
cout<<f[m];
return 0;
}
分组背包
原题链接：https://www.acwing.com/problem/content/9/
题意：
有n组物品和容量是m的背包。每组物品有若干个，同一组的物品只能选择一个，每件物品的体积是vij，价值是wij，i是组号，j是组内编号。求将哪些物品装入背包里，可以使物品的总体积不超过背包容量，且总价值最大。
思路：
f[i][j]表示在前i个物品中选，体积不超过j的选法的最大价值。
那么我们只需要在01背包的基础上多加一层循环，循环每组内的每个物品就可以了。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=105;
int f[N][N];
int s[N];
int v[N][N],w[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=1;j<=s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
for(int k=1;k<=s[i];k++){
if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m];
return 0;
}
变形：金明的预算方案
原题链接：https://www.acwing.com/problem/content/489/
题意：
有n个想买的物品，m元钱。每个物品要么是主件，要么是从属于某个主件的附件，要买一个附件的话必须要买他的主件。每个主件最多有两个附件。每个物品的价格是vi，重要度是wi，编号是p，当p=0时他就是主件，当p>0时这个物品是从属于p的附件。求在买的东西的总价格不超过m的情况下，所有物品的价格和重要度的乘积和的最大值。
思路：
把每个主件都看成一个组，对于所有组最多只有4种情况：
只选主件
选主件和附件1
选主件和附件2
选主件和附件1附件2
那么实际上就是对每组选一种情况，实质就是分组背包问题。
我们用二进制枚举来枚举选了哪些附件，最后如果选择的物品的体积小于我们枚举的不超过的体积，那么就可以更新。
#include<bits/stdc++.h>
#include<vector>
using namespace std;
typedef pair<int,int> pii;
const int N=32005;
int f[N];
vector<int> ma;
vector<pii> son[70];
int n,m;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){
int v,p,q;
cin>>v>>p>>q;
if(q==0){
ma.push_back(i);
son[i].push_back({v,p});
}else{
son[q].push_back({v,p});
}
}
for(int i=0;i<ma.size() ;i++){
int id=ma[i];
for(int j=m;j>=son[id][0].first;j--){
if(son[id].size() ==1){
int v=son[id][0].first;
int w=son[id][0].second;
if(v<=j)f[j]=max(f[j],f[j-v]+v*w);
}else if(son[id].size() ==2){
int v=son[id][0].first;
int w=son[id][0].second;
int v1=son[id][1].first;
int w1=son[id][1].second;
if(v<=j)f[j]=max(f[j],f[j-v]+v*w);
if(v+v1<=j)f[j]=max(f[j],f[j-v-v1]+v*w+v1*w1);
}else{
int v=son[id][0].first;
int w=son[id][0].second;
int v1=son[id][1].first;
int w1=son[id][1].second;
int v2=son[id][2].first;
int w2=son[id][2].second;
if(v<=j)f[j]=max(f[j],f[j-v]+v*w);
if(v+v1<=j)f[j]=max(f[j],f[j-v-v1]+v*w+v1*w1);
if(v+v2<=j)f[j]=max(f[j],f[j-v-v2]+v*w+v2*w2);
if(v+v2+v1<=j)f[j]=max(f[j],f[j-v-v2-v1]+v*w+v2*w2+v1*w1);
}
}
}
cout<<f[m];
return 0;
}
分组背包求具体方案
例题：机器分配
原题链接：https://www.acwing.com/problem/content/1015/
题意：
有n个公司，一共有m个机器。现在要把这m个机器分给n个公司，每个公司可以分配任意数量的机器，但是所有分配给公司的机器总和不能超过m。当第i个公司分配j台设备的时候，会有w[i][j]的盈利。那么求满足条件的任意一个分配方案，并且输出最大盈利。
思路：
f[i][j]表示分配给前i个公司恰好m个机器的最大价值
对于每个公司枚举分配的个数k，那么转移方程:f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k])
那么最大价值其实是在前n个公司之中恰好分配0~m个机器的最打价值，那么最大价值=max(f[n][i]),并且记录取最大价值的时候恰好取的总机器数cnt
那么我们在求具体方案的时候，由于f[i][j]是由f[i-1][j-k]+w[i][k]转换而来，我们就可以从n开始向1枚举前i个公司，再从0~m枚举第i个公司分配的机器数j，当f[i][cnt]=f[i-1][cnt-j]+w[i][j]的时候，说明当i公司取到j个机器的时候可以转换到最大值，那么记录一下j，cnt(表示前i个公司取得最大价值的时候恰好取的总共机器数)再减去j，由此可得出具体方案
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20,INF=1e9;
int f[N][N];
int mp[N];
int n,m;
int w[N][N];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>w[i][j];
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=-INF;
}
}
for(int i=0;i<=n;i++){
f[i][0]=0;
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k]+w[i][k]);
}
}
}
int cnt=0,ww=0;
for(int i=0;i<=m;i++){
if(f[n][i]>=ww){
ww=f[n][i];
cnt=i;
}
}
for(int i=n;i>=1;i--){
for(int j=0;j<=m;j++){
if(f[i-1][cnt-j]+w[i][j]==f[i][cnt]){
mp[i]=j;
cnt-=j;
break;
}
}
}
cout<<ww<<endl;
for(int i=1;i<=n;i++){
cout<<i<<" "<<mp[i]<<endl;
}
return 0;
}
有依赖的背包问题
原题链接：https://www.acwing.com/problem/content/10/
题意：
有n个物品和容量为m的背包，物品之间有依赖关系，依赖关系组成一个树的形状，如果选择一个物品，那么必须选择他的父节点。
第i件物品体积是vi，价值是wi，依赖的父节点编号是pi。
求解将哪些物品放入背包中可以满足题意且总价值最大。
思路：
树形dp
如果我们想在一个以i为根的子树中选物品，那么我们必须得选根节点。
f[u][j]表示所有从以u为根节点的子树中选，必选u且总体积不超过j的方案的最大价值。
因为u是必选的，所以我们预留u的体积，j从0~m-v[u]，先算u所连的子结点son的子树能达到的最大价值。
那么对于他的每个子节点son，枚举所占的体积k，相当于一个分组背包，每个子结点为一组，在一组中选择一个所占的体积。
对于分组背包的状态转移方程是：f[i][j]=max(f[i-1][j],f[i-1][j-v[i][k]]+w[i][k])
由于都是从第i-1层转移过来的，那么我们就将他的体积从大到小枚举
那么最终的状态转移方程就是:f[u][j]=max(f[u][j],f[u][j-k]+f[son][k])
这个时候算出的最大价值是没有加上u的最大价值，那么我们就将体积j大于v[u]的状态用j-v[u]更新一下，加上u的价值即可。
那么同理，小于v[u]的状态值是0。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=400;
int n,m;
int f[N][N];
int v[N],w[N];
int e[N*2],h[N],ne[N*2];
int idx;
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u){
for(int i=h[u];i!=-1;i=ne[i]){
int son=e[i];
dfs(son);
for(int j=m-v[u];j>=0;j--){//预留u的体积
for(int k=0;k<=j;k++){//枚举子树所占的体积
f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
}
}
}
for(int j=m;j>=v[u];j--) f[u][j]=f[u][j-v[u]]+w[u];
for(int i=0;i<v[u];i++) f[u][i]=0;
}
signed main(){
cin>>n>>m;
memset(h,-1,sizeof h);
int root=-1;
for(int i=1;i<=n;i++){
int p;
cin>>v[i]>>w[i]>>p;
add(p,i);
if(p==-1) root=i;
}
dfs(root);
cout<<f[root][m];
return 0;
}
二维费用的背包问题
宠物小精灵之收服
原题链接：https://www.acwing.com/problem/content/1024/
题意：
有n个小精灵，要收服第i只小精灵的话需要v[i]个精灵球和p[i]个体力，我们有m个精灵球和p个体力，当收服一个小精灵将我们的体力变成一个小于等于0的数的时候，我们停止收服，当精灵球用完的时候，我们停止收服。问最多能收服多少小精灵。
思路：
f[i][j][k]表示在前i个小精灵中，花费的精灵球数不超过j，损失的体力不超过k的情况下，能收服的小精灵的最多个数。
那么对于每个小精灵有两种选择：选或者不选。
不选：f[i][j][k]=f[i-1][j][k];
选：f[i][j][k]=f[i-1][j-v[i]][k-w[i]]+1
那么整理之后的代码就是：
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=1;k<=p;k++){
f[i][j][k]=f[i-1][j][k];
if(j>=v[i]&&k>=w[i]) f[i][j][k]=max(f[i-1][j-v[i]][k-w[i]]+1);
}
}
}
但是三维的数组会爆空间，那么我们注意到每次实际上更新i只用了第i-1层的数，所以我们用优化01背包的方法，将j和k反着求就好了。
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
for(int k=p;k>=w[i];k--){
f[j][k]=max(f[j-v[i]][k-w[i]]+1,f[j][k]);
}
}
}
最后需要注意的是，如果说一个小精灵收服后体力值变为0，那么我们就不能收服这个小精灵，那么我们可以求当收到的伤害不超过p-1的时候能收服的最多的小精灵的数量，即f[m][p-1]。并且求最多剩余体力，那么我们就看等于答案的最小收到的伤害con，再用总体力减去con就可以了。
#include<bits/stdc++.h>
using namespace std;
int n,m,p;
int f[1005][505];
int v[105],w[105];
int main(){
cin>>m>>p>>n;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
for(int k=p;k>=w[i];k--){
f[j][k]=max(f[j-v[i]][k-w[i]]+1,f[j][k]);
}
}
}
int ans=f[m][p-1];
int con;
for(int i=0;i<=p;i++){
if(ans==f[m][i]){
con=i;
break;
}
}
cout<<ans<<" "<<p-con<<endl;
return 0;
}
潜水员
原题链接：https://www.acwing.com/problem/content/1022/
题意：
有n个气缸，每个气缸都装有两种气体：氧气和氮气，还有相应的气体容量。第i个气缸中有容量为v1[i]的氧气和v2[i]的氮气，他的重量是w[i]。那么求至少装容量为m1的氧气和容量为m2的氮气时，选择的气缸的重量的最小值。
思路：
f[i][j1][j2]表示在前i个物品中选，氧气的体积至少为j1，氮气体积至少为j2的情况下，选择的气缸重量的最小值。
不选第i个物品：f[i-1][j1][j2]
选第i个物品：f[i-1][j1-v1[i]][j2-v2[i]]
因为要求最小值，初始化的时候把所有值都赋值成极大值，将f[0][0][0]赋值成0.
那么我们在转移的时候，从j-v转移过来的时候，如果j-v是负数，那么这个状态也是合法的，表示为如果容量至少为负数的时候，所选气缸的最小重量。
换一种说法，当j-v<0的时候表示v>j，那么选了这个物品之后肯定满足至少为j，那么我们就不需要选之前的物品，那么就按照之前的物品的容量至少为0来算就可以了。
核心代码：
memset(f,0x3f,sizeof f);
f[0][0][0]=0;
for(int i=1;i<=n;i++){
for(int j1=0;j1<=m1;j1++){
for(int j2=0;j2<=m2;j2++){
f[i][j1][j2]=f[i-1][j1][j2];
f[i][j1][j2]=min(f[i-1][max(0ll,j1-v1[i])][max(0ll,j2-v2[i])]+w[i],f[i][j1][j2]);
}
}
}
优化一维之后的代码是：
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
int n,m1,m2;
int f[30][85];
signed main(){
cin>>m1>>m2;
cin>>n;
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
int v1,v2,w;
cin>>v1>>v2>>w;
for(int j1=m1;j1>=0;j1--){
for(int j2=m2;j2>=0;j2--){
f[j1][j2]=min(f[j1][j2],f[max(0ll,j1-v1)][max(0ll,j2-v2)]+w);
}
}
}
cout<<f[m1][m2]<<endl;
return 0;
}
货币系统
原题链接：https://www.acwing.com/video/388/
题意：
有n种面额的货币，第i种货币的面额为a[i]，每种货币有无数张。那么我们将这n种货币能凑成的全部面额称为一个货币系统，记为（n,a)。那么我们要找到一个货币系统(m,b)，m尽可能小，使得这个货币系统和(n,a)这个货币系统凑成的数值相等。
思路：
可以发现a数组中的每个数，都可以被b数组中的一些数凑出来。
在最优解中，b都是从a数组中选择出来的。
那么较大的数是被较小的数凑出来的，那么我们先将a数组从小到大排序之后，再对每个数进行考虑。
对第i个数来说，我们需要判断的是它能否被前面的数（1~i-1）凑出来，如果能被凑出来说明不能选择他，不能凑出来的话说明必须要选择他。
将每个数看成一种有无数个的物品，将他们的和看成是背包的容积，那么看能不能凑出a[i]，实际上就是看用前i-1种物品是否能凑出来体积等于a[i]的容量。
其实就是判断一下，装满a[i]的方案数是不是0.
f[i][j]表示能从前i个数中凑出j的方案数。那么我们只需要做一遍完全背包求方案数，然后判断每个f[i-1][a[i]]是否等于0就可以了。
朴素做法容易超时且爆空间，那么我们就优化一维，然后判断对于每个f[a[i]]的方案数是否等于1就可以了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p;
int f[25005];
int a[105];
void sove(){
cin>>n;
int mx=0;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=max(mx,a[i]);
}
for(int j=0;j<=mx;j++){
f[j]=0;
}
f[0]=1;
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
for(int j=a[i];j<=mx;j++){
f[j]+=f[j-a[i]];
}
}
int con=0;
for(int i=1;i<=n;i++){
if(f[a[i]]==1) con++;
}
cout<<con<<endl;
}
signed main(){
int t;
cin>>t;
while(t--){
sove();
}
return 0;
}
混合背包问题
原题链接：https://www.acwing.com/problem/content/7/
有n种物品和一个容量是m的背包，类型有3种：
1.第一种物品只能用一次
2.第二种物品可以用无限次
3.第三种物品只能用si次
求物品体积总和不超过背包容量，能装的最大价值。
思路：
完全背包的转移公式：f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i])
多重背包的转移公式：f[i][j]=max(f[i][j],f[i-1][j-kv[i]]+kw[i])
01背包是特殊的多重背包，将si设为1即可
那么对于多重背包，我们将他进行一个二进制优化，将他分成多个背包之后，再对每个背包进行01背包的转换。
#include<bits/stdc++.h>
using namespace std;
const int N=2000;
int n,m;
int f[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
if(s==0){
for(int j=v;j<=m;j++){
f[j]=max(f[j],f[j-v]+w);
}
}else{
if(s==-1) s=1;
for(int k=1;k<=s;k*=2){
for(int j=m;j>=k*v;j--){
f[j]=max(f[j],f[j-k*v]+w*k);
}
s-=k;
}
if(s>0){
for(int j=m;j>=s*v;j--){
f[j]=max(f[j],f[j-s*v]+s*w);
}
}
}
}
cout<<f[m];
return 0;
}
背包问题求方案数
原题链接：https://www.acwing.com/problem/content/11/
题意：
n个物品，一个容量为m的背包，每个物品体积为vi，价值为wi，只能用一次，求所选择的物品总体积不超过背包容量时得到的最大价值的方案数，对1e9+7取模。
思路：
f[i][j]表示前i个物品中选，体积恰好是j的最大价值。
转移方程：f[i][j]=max(f[i-1][j],f[i-1][j-vi]+wi);
g[i][j]表示当f[i][j]取到最大值时的方案数。
那么我们就判断f[i-1][j]和f[i-1][j-vi]哪个大：
如果f[i-1][j]大，那么方案数就加上g[i-1][j]
如果f[i-1][j-vi]大，那么方案数就加上g[i-1][j-vi]
如果一样大，那么就加上g[i-1][j]和g[i-1][j-vi]
注意：对于每个选择来说，不选择也是一种方案，所以我们在初始化的时候将所有不选择的方案数都初始化为1：
g[i][0]：前i个物品中选体积不超过0的方案就是不选
g[0][i]：前0个物品中体积不超过i的方案也是不选
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int n,m;
const int N=1005;
int f[N][N];
int g[N][N];
int v[N],w[N];
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
memset(f,-0x3f,sizeof f);
for(int i=0;i<=n;i++) g[i][0]=1;
for(int j=0;j<=m;j++)g[0][j]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
g[i][j]=g[i-1][j];
if(j>=v[i]){
if(f[i-1][j-v[i]]+w[i]>f[i][j]){
f[i][j]=f[i-1][j-v[i]]+w[i];
g[i][j]=g[i-1][j-v[i]];
}else if(f[i-1][j-v[i]]+w[i]==f[i][j]){
g[i][j]=(g[i][j]+g[i-1][j-v[i]])%mod;
}
}
}
}
cout<<g[n][m]<<endl;
return 0;
}
背包问题求具体方案
原题链接：https://www.acwing.com/problem/content/12/
题意：
n个物品，容量为m的背包，每个物品的体积是vi，容量是wi，只能选一次，求在不超过背包的体积的条件下，能选择的物品的总价值最大的方案。输出字典序最小的方案。
思路：
要求字典序最小的话，我们需要从前往后考虑，在考虑第i个物品的时候：
如果只能不选，就不选
只能选，就选
可以选也可以不选，就得选（不选的话字典序会变大）
我们在状态转移的时候，如果从前往后转移就没有办法从前往后找字典序最小的方案，那么我们需要从后往前转移：从第n个物品到第1个物品考虑选或者不选，那么这个时候的f[i][j]就表示在后i个物品中选，体积不超过j的方案的最大价值。转移方程为：
f[i][j]=max(f[i+1][j],f[i+1][j-v]+w)
那么最后我们求得的f[1][m]实际上就是最大值。
将背包剩下的体积j设为m，当前遍历的背包设为1，背包从1开始遍历，当遍历到第i个背包的时候，剩余的体积j如果大于这个背包，我们就考虑选择不选择这个背包：选这个背包的价值是f[i+1][j-v[i]]+w[i]，不选这个背包的价值是f[i+1][j]，如果选择这个背包的价值大于等于不选，那么我们就选。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=1005;
int f[N][N];
int g[N][N];
int v[N],w[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
for(int i=n;i>=1;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]);
}
}
int j=m;
for(int i=1;i<=n;i++){
if(j>=v[i]){
if(f[i+1][j-v[i]]+w[i]>=f[i+1][j]){
cout<<i<<" ";
j-=v[i];
}
}
}
return 0;
}