2144 砝码称重 2

 时间限制: 1 s

 空间限制: 16000 KB

 题目等级 : 钻石 Diamond

 

题目描述 

Description

有n个砝码，现在要称一个质量为m的物体，请问最少需要挑出几个砝码来称？

注意一个砝码最多只能挑一次

输入描述 

Input Description

第一行两个整数n和m，接下来n行每行一个整数表示每个砝码的重量。

输出描述 

Output Description

输出选择的砝码的总数k，你的程序必须使得k尽量的小。

样例输入 

Sample Input

3 10

5

9

1

样例输出 

Sample Output

数据范围及提示 Data Size & Hint

1<=n<=30，1<=m<=2^31，1<=每个砝码的质量<=2^30

【思路】

正解：搜索

神正解：双向搜索

吐槽：你都知道质量是m了你称个鬼啊╭(╯^╰)╮

【code】

我的智障搜索

#include
      
       #include
       
        using namespace std;int w[35],use[50];long long ans,m;int n,res=2147483647;void dfs(int x){    if(ans>=res){        return;    }    if(!m)    {        if(ans
       
      

比较尴尬.....

用后缀和优化 剪枝

#include
      
       #include
       
        #include
        
         using namespace std;long long  w[50],last[50];int n,m;int ans;inline int read(){    int f=1,x=0;char ch=getchar();    while(ch<'0'||ch>'9'){
    if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return f*x;}inline bool cmp(int a,int b){    return a>b;}inline void dfs(int now,int use,long long ww){    if(use>=ans)return;    if(ww==m){ans=min(ans,use);}    for(int i=now+1;i<=n;i++)    {        if(ww+last[i]
         
          m)continue;         dfs(i,use+1,ww+w[i]);    }    return; }int main(){    n=read();m=read();    for(int i=1;i<=n;i++)    w[i]=read();    sort(w+1,w+n+1,cmp);    for(int i=n;i>=1;i--)    last[i]=last[i+1]+w[i];    ans=n;    dfs(0,0,0);    printf("%d\n",ans);    return 0;}
         
        
       
      

发现加上inline也没多大用。（前后对比）

比较神的双向搜索，其实我做这个题就是为了学这个方法。

就是把原来的数分成两部分进行dfs。

并用map<int,int>这些质量需要多少砝码。

mm-sum能在第一次dfs中能找到。（sum表示第二次dfs中目前总质量）

js+m[mm-sum];来更新最优解。

#include
      
       #include
       
        #include
        
         #include