题解 | 【模板】01背包（计数）

#include<bits/stdc++.h>
using namespace std;

using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

const int MOD=1e9+7;

void solve()
{//由于数据量比较大 我们需要使用空间优化 
//设置两个数组 一个dp[j]表示当容量为j时可取到的最大价值
//一个cnt[j]表示当容量为j时可取到的最大方案数
//和01背包基本思路一样
//当dp[j]<dp[j-w[i]]+v[i] 我们更新dp[j]和cnt[j]
//注意更新后的cnt[j]不一定比原来的大
//当dp[j]=dp[j-w[i]]+v[i] 我们令cnt[j]的方案数累积
//即加上cnt[j-w[i]]
	int n,m;
	cin >> n >> m;
	vector<int>dp(m+1,0),cnt(m+1,1),w(n+1,0),v(n+1,0);
	for(int i=1;i<=n;i++) cin >> w[i] >> v[i];
	for(int i=1;i<=n;i++)
	{
		for(int j=m;j>=w[i];j--)
		{
			if(dp[j]<dp[j-w[i]]+v[i])
			{
				dp[j]=dp[j-w[i]]+v[i];
				cnt[j]=cnt[j-w[i]];
			}
			else if(dp[j]==dp[j-w[i]]+v[i])
			{
				cnt[j]=(cnt[j]+cnt[j-w[i]])%MOD;
			}
		}
	}
	cout << cnt[m] << "\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	cin >> t;

	while(t--)
	{
		solve();
	}
	return 0;
}