背包问题的方案总数
对于一个给定了背包容量、物品费用、物品间相互关系（分组、依赖等）的背包问题，除了再给定每个物品的价值后求可得到的最大价值外，还可以得到装满背包或将背包装至某一指定容量的方案总数。
对于这类改变问法的问题，一般只需将状态转移方程中的max改成sum即可。
例如若每件物品均是01背包中的物品，转移方程即为f[i][v]=sum{f[i-1][v],f[i-1][v-w[i]]+c[i]}，初始条件f[0][0]=1。
事实上，这样做可行的原因在于状态转移方程已经考察了所有可能的背包组成方案。
对于一般背包问题，既然我能从所有的解中找出最优解，那么我必然是已经知道了所有的解的。
而对于背包问题，每一个状态无非就是两种情况：取、不取。所以在计算方案的时候，我就把取或者不取加上来就好了。
看例题：
【例9-17】、货币系统
【问题描述】
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。样例：设n=3，m=10，要求输入和输出的格式如下：
【样例输入】money.in
3 10 //3种面值组成面值为10的方案
1 //面值1
2 //面值2
5 //面值5
【样例输出】money.out
10 //有10种方案
【算法分析1】
设f[j]表示面值为j的总方案数，如果f[j-a[i]]!=0则f[j]=f[j]+f[j-a[i]],1<=i<=n,a[i]<=j<=m。
f[j-a[i]]!=0说明j>=a[i]，因为f[0]=1，也就是我的剩余金额还支持我取这张金额。
f[j]=f[j]+f[j-a[i]]，f[j-a[i]]表示取第i这张钞票，f[j]表示我不取这张钞票。所以情况就是两者之和。
下面的代码就是从上往下、从前往后依次填满这个n*m（这里用一维数组优化了）的表格。
有点完全背包的意思再里面。
这种写法的思路：选或者不选这种钞票，而不管到底选几张。因为从前往后的这种写法会帮我取好多张。
1 #include<cstdio> 2 using namespace std; 3 4 int n, m; 5 int a[101]; 6 long long f[10001]; 7 8 int main(){ 9 scanf("%d%d",&n,&m); 10 for (int i = 1; i <= n; i++) 11 scanf("%d",&a[i]); 12 f[0] = 1; 13 for (int i = 1; i <= n; i++)//前i种钞票 14 for (int j = a[i]; j <= m; j++) 15 f[j] += f[j-a[i]]; 16 printf("%lld",f[m]); 17 return 0; 18 }
【算法分析2】
设f[j]表示面值为j的最大方案数， 如果f[j-k*a[i]]!=0则f[j]=f[j]+f[j-k*a[i]]，当1<=i<=n，m>=j>= a[i]，1<=k<=j / a[i]。
f[j]=f[j]+f[j-k*a[i]]这个状态转移方程，很明显是分组背包的写法。
当然，这里等式右边的的f[j]还是不选i这种钞票的情况，f[j-k*a[i]]这部分表示选i这种钞票的情况。
既然选这张钞票，那么下标肯定是从1开始，也就是最少选一张。
这里还要分析一个问题：为什么代码里面j是从m->a[i]，而不是从a[i]到m。
显然，这样倒过来写的方式一般是不希望后面的数据被前面的数据影响。
注意我在这里已经枚举k，也就是枚举了第i种钞票我取几张的情况。
如果这里我们让i==1，也就是现在只取第一种钞票，假设面值为1，
如果j从m->a[i]，可以保证所有的f[j]都为1。
如果j从a[i]到m，当j=1是，f[1]=1，当j=2时，k为1或者2，当k=1是，f[2]=f[2]+f[1]=1,当k=2是，f[2]=f[2]+f[0]=2这个答案显然不对。
其实总结一下：
对于背包问题，如果不是完全背包，将二维状态f[i][j]优化到一维状态f[j]的话，一定要保证前面的数据不影响后面的，所以一定要保证j从后往前。
如果是二维状态f[i][j]，j的方向随意，因为这样是在上一行取值，而不是用当前行可能已经被修改的值。
如再有不懂，请仔细分析i，j，k的循环情况，结合实际意义思考，或者把f[j]表格画出来分析。或者降维分析。
93分，有一个点超时
1 #include<cstdio> 2 int m, n; 3 int a[1001]; 4 long long f[10001]; //注意要用long long 5 6 int main() 7 { 8 scanf("%d%d",&n,&m); //n种面值的货币，组成面值为m 9 for (int i = 1; i <= n; i++) 10 scanf("%d",&a[i]); //输入每一种面值 11 f[0] = 1; 12 for (int i = 1; i <= n; i++) 13 for (int j = m; j >= a[i]; j--) //f[j]表示面值为j的总方案数 14 for (int k = 1; k <= j / a[i]; k++) 15 f[j] += f[j-k*a[i]]; 16 printf("%lld",f[m]); // f[m]为最优解 17 return 0; 18 }