背包问题到现在讲到第八讲——求方案数，那就是在01背包、多重背包、完全背包基础上来求方案数，具体描述为如下：
这里用acwing上的01背包基础上求方案数：11. 背包问题求方案数 - AcWing题库
这既然是01背包基础上改进，那代码就在01背包基础上改进的，选择加一个c[i]数组记录方案数。
代码语言：javascript复制#include<iostream>
using namespace std;
const int mod=1e9 7;
int n,m;
int v[1005],w[1005];
int f[1005],c[1005];
//f[i]表示背包容量为i时所获得最大价值，c[i]表示背包容量为i时的方案数
int main(){
cin>>n>>m;
for(int i=0;i<=m;i ){
c[i]=1;//什么也不选，自己也是一种方案
}
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--){
if(f[j]<f[j-v[i]] w[i]){//如果选第i件物品价值更大，那就选择，此时价值改变，方案数不变
f[j]=f[j-v[i]] w[i];
c[j]=c[j-v[i]];
}else if(f[j]==f[j-v[i]] w[i]){//如果价值相等，获得此价值相对又多了一种方案，方案数相加
c[j]=(c[j] c[j-v[i]])%mod;
}
}
}
cout<<c[m]<<endl;
return 0;
}这里解释一下状态转移方程，f[j]<f[j-v[i]] w[i]时，说明选择第i个物品价值更大，那就选择，选择了背包容量就要扣除v[i]留给选择第i件物品，相对于背包容量j-v[i]背包容量增加了，选择了它并不会改变方案数，你可以理解一棵树，向左选择，向右不选，当此时背包容量相同时，分别走不同的分支是不同的方案，但是位于同一分支处，面临选不选，我的方案数是不变的，因为选了背包容量就增大了，方案数是在背包容量相等的基础上而言。
所以此时总结一下：
装入新物品，若总价值增大，则更新f[i]和c[i]
装入新物品，若总价值不变，则更新c[i]
装入新物品，若总价值减小，则不用更新
此题你会发现，当背包容量不同时可能会产生同样的最大价值，如果再考虑上背包容量恰好装满时呢
最开始我们想到的就是在if上多加上一个限定条件，一个很巧妙的方法我们可以在初始化上做一下手脚，保证状态转移可以在c[0]上转移。使得只有恰好装满时才有机会通过c[0]去直接或者间接转移。那些不符合条件的，不能装满的都被过滤掉了，具体大家可以debug看一下过程。
以上是01背包基础上，完全背包、多重背包的话，也在其基础上修改，例如在完全背包时，唯一改变就是遍历时正序遍历了。
编者水平有限，介绍的不是很详细，若有不明白、不理解的地方随时可以问我，我会尽力给大家解答，下篇更新背包问题求具体方案。
