海洋之心


私信TA

用户名:wanggongsheng

访问量:122491

签 名:

等  级
排  名 17
经  验 20493
参赛次数 3
文章发表 163
年  龄 26
在职情况 学生
学  校
专  业 计算机技术

  自我简介:

读研ing,平时不登录dotcpp

解题思路:

注意事项:

参考代码:

dfs不超时是没有想到的

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
int n,m,A[25],w[11],res;
void dfs(int dep,LL sum,int& res,int w)
{
	if(res) return;//如果找到了合适的称量方法,直接返回,不用继续搜索 
	if(sum==w)//如果满足重量 
	{
		res=true;
		return ;
	}
	if(dep<=n)
	{
		dfs(dep+1,sum+A[dep],res,w);
		dfs(dep+1,sum,res,w);
		dfs(dep+1,sum-A[dep],res,w);	
	} 
} 
int main(void)
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<=m;i++) cin>>w[i];
	for(int i=1;i<=m;i++)
	{
		res=false;
		dfs(1,0,res,w[i]);
		if(res) cout<<"YES"<<endl;
		else cout<<"NO"<<endl; 
	}
	return 0;
}


 

0.0分

4 人评分

  评论区