题解 1548: 蓝桥杯算法提高VIP-盾神与砝码称重 （DFS 深度优先搜素）

上面是一个当砝码为8，4，2，1 四个砝码时的搜索情况 ，物品我们假设是放在天平的左边的，我们可以把砝码放在天平的左边 也可以放在天平的右边  ，分别代表着 +w[i] 和 -w[i] 直到我们要称的重量为0了 便称出了该物体 的重量。本题一个关键点就是你要遍历所有的放置情况   这样就涵盖了 所有砝码的放置情况 。比如 放置了8  后面就考虑4，2，1的放置情况  放置完4后 就考虑放置2，1的情况  而不用考虑放置8的情况  因为前面在放置8时  后面包括了放置4的情况  

由于我对深度搜索了解的也不多 欢迎大家批评指正 一起学习！！（图画的有点丑。。）

#include<iostream>  
#include<algorithm>  
#include<string.h>  
#include<cmath>   
using namespace std;  
int n,m,flag;  
int w[25],k[25]={0};  
bool cmp(const int &x, const int &y)  
{  
    return x > y;   
}  
void dfs(int s,int x)  //好了 关键来了
{  
    if (flag){ //退出条件   
        return ;  
    }  
     
    if (s == 0)  //s等于0表示称出了结果
    {  
        flag = 1;  
        return ;  
    }  
    if (abs(s)>k[x]){//如果物品的重量大于剩下的砝码能表示的最大重量 
        return ;  
    }  
     
    for (; x<n; x++)  //每个x表示搜索的起点
    {  
        //两种情况   
        dfs(s-w[x],x+1);  //把砝码放在天平的右边
        dfs(s+w[x],x+1);  //把砝码放在天平的左边
    }  
}  
int main()  
{  
    int s;  
    cin>>n>>m; //输入砝码和物品的个数
    for (int i=0; i<n ;i++)  
    {  
        cin>>w[i];  //输入砝码的重量
    }  
    sort(w,w+n,cmp);  //将砝码从大到小排序
    //集合砝码和   
    for (int i=n-1; i>=0; i--)  
    {  
        k[i] = w[i]+k[i+1];  //依次求出前（n-i）个砝码能称出的最大重量
    }   
    while (m--)  
    {  
        cin>>s;  //输入待称物品的重量
        flag = 0; //flag=0表示未称出
        dfs(s,0);  
        if (flag){  //flag=1表示称出了物品重量
            cout<<"YES"<<endl;            
        } else{  
            cout<<"NO"<<endl;  
        }  
    }  
    return 0;  
}