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

解题思路:

可以用DFS

注意事项:

1.还好数据量小，数据量大可能还是要DP做

2.天平两边都可以放砝码，和物体放在同侧相当于减

3.不能用判断当前质量是否小于零，或者当前选择砝码的质量大于物体质量来剪枝

参考代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <cctype>

#define N 24

using namespace std;

int weight[N + 2];
int obj[N + 2];
bool able[N + 2];

void DFS(int cur, int curWeight, const int tgtWeight, const int n, const int objNo)
{
	if (cur > n)
		return;
	else if (curWeight == tgtWeight)
	{
		able[objNo] = true;
		return;
	}
	else
	{
		//砝码和物品分开放
		DFS(cur + 1, curWeight + weight[cur], tgtWeight, n, objNo);
		//不放
		DFS(cur + 1, curWeight, tgtWeight, n, objNo);
		//砝码和物品放一起
		DFS(cur + 1, curWeight - weight[cur], tgtWeight, n, objNo);
	}
}

int main(int argc, char** argv)
{
	int n = 0, m = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> weight[i];
	for (int i = 0; i < m; i++)
		cin >> obj[i];
	for (int i = 0; i < m; i++)
		DFS(0, 0, obj[i], n, i);
	for (int i = 0; i < m; i++)
	{
		if (able[i] == true)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}