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

解题思路:

    可以用DFS实现。天平两边都可以放砝码。所以砝码有三种状态。

    定义一个函数：bool opt(int n,int total,int w)

    其中：n表示剩余砝码个数，total表示能称重量，w表示物品重量

    1.把第n个砝码放在物品另一侧，则有：opt(n-1,total+fama[n-1],w)

    2.把第n个砝码放在与物品同侧，择有：opt(n-1,total-fama[n-1],w)

    3.不放第n个砝码，则有：opt(n-1,total,w)

参考代码:

#include <bits/stdc++.h>
using namespace std; 
const int N=25;
const int M=11;
int fama[N]; //砝码重量 
bool opt(int n,int total,int w)  //n表示剩余砝码个数，total表示能称重量，w表示物品重量 
{
	if(n<0) return false;
	if(total==w) //如果总重量等于物体重量 
		return true;
	bool A=opt(n-1,total+fama[n-1],w); //把第n个砝码放在物品另一侧 
	bool B=opt(n-1,total-fama[n-1],w); //把第n个砝码放在与物品同侧  
	bool C=opt(n-1,total,w);           //不放第n个砝码
	return A||B||C;
}
int main()         
{ 
	int n,m;
	int weight[M]; //物品重量 
	bool yesno[M]; //是否能称出来
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>fama[i];
	for(int i=0;i<m;i++)
	{
		cin>>weight[i];
		yesno[i]=opt(n,0,weight[i]); //把该物品是否能称出来的标志放到数组中保存，最后才一起输出
	}
	for(int i=0;i<m;i++)   //输出第i个物品能否称出来的标志
	{
		if(yesno[i])
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl; 
	}
	return 0;
}