背包问题到现在讲到第八讲——求方案数，那就是在01背包、多重背包、完全背包基础上来求方案数，具体描述为如下：
这里用acwing上的01背包基础上求方案数：11. 背包问题求方案数 - AcWing题库
这既然是01背包基础上改进，那代码就在01背包基础上改进的，选择加一个c[i]数组记录方案数。
#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背包基础上，完全背包、多重背包的话，也在其基础上修改，例如在完全背包时，唯一改变就是遍历时正序遍历了。
编者水平有限，介绍的不是很详细，若有不明白、不理解的地方随时可以问我，我会尽力给大家解答，下篇更新背包问题求具体方案。
