dfs-砝码称重问题

解题思路：利用dfs进行深度搜索：已知最终的目的（15 16），给出路径（1 2 4 8）

设置货物中 G “+”代表左边，“-”表示右边 

结束条件：G == 0；设置 flag=0表示 是否可以完成最终的目的。

这样我们可以确定 dfs递归的公式

***解题关键：for(int w=0;w<n;i++)

                        {

                            dfs(G+weigth[w],w+1);

                            dfs(G-weigth[w],w+1);

                        }

递归的返回值：if(G>sum)return ;首先应该保证：货物的总量不大于 砝码的质量 

                       if(g==0)

                        {flag=1;return;***结束条件

#include<bits/stdc++.h>

using namespace std;

int flag=0;int n,m;int data[20];

int sum;

void dfs(int g,int w)

{

if(g>sum)return;

if(g==0)

{

flag=1;

return ;

}

for(;w<n;w++)

{

dfs(g+data[w],w+1);

dfs(g-data[w],w+1);

}

}

int main()

{

cin>>n>>m;

for(int i=0;i<n;i++)

{

cin>>data[i];

sum+=data[i];

}

while(m--)

{

int s;

cin>>s;

dfs(s,0);

if(flag)

{

cout<<"Yes"<<endl;

flag=0;

}else{

cout<<"No"<<endl;

}

} 

return 0;

}

/*

*/