背包问题求装满背包的方案总数

至于我为什么先发方案总数而不是必须装满，说多了都是泪，我上次写了草稿忘保存了。

回到正题：

求方案总数和求最大价值的区别不是很大，改一下发里面的关系式就可以了，求方案总数不用输入价值只有物品重量，不说那么多，先看公式：

d[j]=d[j]+d[j-w[i]];

求方案总数和求最大价值不同，求最大价值，是不断选取更优的方案（其实就是dp动态规划），而求方案总数则是通过累加，我有方案就+1的原理得出结果；

有一个前提是；

我们要初始化d[0]=1;因为j表示背包内剩余的重量，而如果我j把东西装满了，是不是就代表背包剩余重量(j)是0，我就多了一种方案。

直接上代码：

d[0]=1;
//先是01
for(int i=1;i<=n;i++)
	{
		for(int j=v;j>=0;j--)
		{
			if(j>=w[i])
			{
				d[j]=d[j]+d[j-w[i]];
			}
		}
	}
//完全
for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=v;j++)
		{
			if(j>=w[i])
			{
				d[j]=d[j]+d[j-w[i]];
			}
		}
	}
cout< 
好了，就是这么多，我要去找必须装满的草稿了。