[Acwing] 11. 背包问题求方案数 01背包求解方案数

前言

前面碰到的一题是 能装下的所有方案

这里是最大的情况

传送门 :

思路

怎么说这题都应该有一个 c n t cnt cnt数组

表示发生状态转移时候的方案计数

但是竟然不是根据乘法原理 *出来的

是加出来的。。。

总之就是 状态转移的时候 c n t [ j ] = c n t [ j − v ] cnt[j] =cnt[j-v] cnt[j]=cnt[j−v]

否则如果相等的话 c n t [ j ] + = c n t [ j − v ] cnt[j]+=cnt[j-v] cnt[j]+=cnt[j−v]

CODE

void solve()
{
	cin>>n>>m;
	for(int i=0;iv>>w;
		
		for(int j = m;j>=v;j--)
		{
			if(f[j]