Luogu p1441 weight weighing

Topic link

#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[25], st[25], f[2005];//a The array represents the weight of the weights , st[i] On behalf of the i Whether a weight has been discarded  1 To be abandoned  0 For not being abandoned , f Backpack for existence 
int dp() {
    
	memset(f, 0, sizeof f);
	f[0] = 1;// Weight is 0 There must be a starting point 
	int res = 0, tot = 0;//res= this dp answer ,tot Total current weight 
	for (int i = 0; i < n; i++)
	{
       
		// st[i]=0  It means not to be abandoned , Then backpack it 
		if (!st[i]) {
    
			for (int j = tot; j >= 0; j--)// At present, the maximum possible weight of the composition is tot
				if (f[j] && !f[j + a[i]])f[j + a[i]] = 1, res++;// If j There is so j+a[i] There must be   Remember not to double calculate 
			tot += a[i];// maintain tot
		}
	}
	return res;
}
void dfs(int i, int now)// The first i Whether to abandon the weight   Currently, the weight quantity has been discarded 
{
    
	if (now > m)return;// Abandon greater than m Cut directly 
	if (i > n)return;// exceed n A weight is also pruned 
	if (i == n && now == m) {
     ans = max(dp(), ans); return; }//  When the conditions are met, run again 01 Existential knapsack 
	dfs(i + 1, now);// The current weight is not discarded , that now unchanged 
		st[i] = 1;dfs(i + 1, now + 1);st[i] = 0;// The current weight is discarded   that st[i]=1 Indicates abandonment of No i A weight ,now+1, Return to the original state after completion 
}
int main()
{
    
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> a[i];
	dfs(0, 0);
	cout << ans << endl;

}