洛谷P1441 砝码称重

题目链接

#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int a[25], st[25], f[2005];//a数组代表砝码重量， st[i]代表第i个砝码是否被舍弃 1为被舍弃 0为不被舍弃， f为存在性背包
int dp() {
    
	memset(f, 0, sizeof f);
	f[0] = 1;//重量为0一定存在作为起点
	int res = 0, tot = 0;//res=此次dp答案，tot当前重量总和
	for (int i = 0; i < n; i++)
	{
       
		// st[i]=0 表示不被舍弃，那么对它进行背包
		if (!st[i]) {
    
			for (int j = tot; j >= 0; j--)//当前最大可能组成的重量为tot
				if (f[j] && !f[j + a[i]])f[j + a[i]] = 1, res++;//如果j存在那么j+a[i]也一定存在 记得不要重复计算
			tot += a[i];//维护tot
		}
	}
	return res;
}
void dfs(int i, int now)//第i个砝码是否舍弃 当前已经舍弃砝码数量
{
    
	if (now > m)return;//舍弃大于m直接剪枝
	if (i > n)return;//超过n个砝码也剪枝
	if (i == n && now == m) {
     ans = max(dp(), ans); return; }// 当满足条件时跑一遍01存在性背包
	dfs(i + 1, now);//当前的砝码不舍弃，那么now不变
		st[i] = 1;dfs(i + 1, now + 1);st[i] = 0;//当前的砝码舍弃 那么st[i]=1表示舍弃第i个砝码，now+1，结束后恢复原状
}
int main()
{
    
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> a[i];
	dfs(0, 0);
	cout << ans << endl;

}