蓝桥杯算法提高VIP-盾神与砝码称重

解题思路:直接dfs，但是这里用到了一个剪枝，降低了时间复杂度

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int n,m;
int x[30];
int flag;
int dfs(int num,int i)
{
    int a;
    if(num==0)//当重量被减为0时说明可以
	{
		return 1;
	}
	else if(i==n)
	{
		return 0;
	}
	flag=dfs(num,i+1)||dfs(num-x[i],i+1)||dfs(num+x[i],i+1);//剪枝如果前面的正确了后面的就不用做了
}
int main()
{
	int Max=0;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>x[i];
		Max+=x[i];
	}
	int w[m+5];
	for(int i=0;i<m;i++)
	{
		cin>>w[i];
		if(Max<w[i])//如果全部砝码加起来都没有物品重的话就说明不可以
		{
			cout<<"NO"<<endl;
			continue;
		}
		dfs(w[i],0);
		if(flag)
		{
			cout<<"YES"<<endl;
			flag=0;
		}
		else
		{
			cout<<"NO"<<endl;
		} 
	}
	return 0; 
}