蓝桥杯算法提高VIP-盾神与砝码称重 （C++代码）dfs

解题思路:dfs三种情况就行了  放物体一边 不放 放物体对面

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int num;
int a[25], sum[25];
int flag = 0;
void fun(int x, int y)
{
	if(flag == 1)
	{
		return ;		
	}
	if(abs(x)>sum[y])///判断以后的砝码是否能称出来现在的重量
        return;
	if(x == 0||abs(x)==sum[y])
	{ 
		flag = 1;
		return ;
	}
	if(y<0)
	{
		return;
	}
	fun(x-a[y], y-1);//不和物品放一起 
	fun(x, y-1);//不放砝码 
	fun(x+a[y], y-1);//放在物品的对立边
	return; 
}
int main()
{
	cin>>n>>m;
	for(int i = 0; i < n; i++)
	{
		cin>>a[i];
		if(i>0)
            sum[i]=sum[i-1]+a[i];///前i个砝码重量和
        else
            sum[0]=a[0];
	}
//	sort(a, a+n);
	for(int i = 0; i < m; i++)
	{
		flag = 0;
		cin>>num;
		fun(num,n-1);
		if(flag == 0)
		{
			cout<<"NO"<<endl;;
		}
		else
		{
			cout<<"YES"<<endl;
		}
	}
	
	return 0;
}