codevs 2144 砝码称重2

传送门

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<iostream>

#include<cstdio>

using namespace std;

int w[],use[];

long long ans,m;

int n,res=;

void dfs(int x)

{

    if(ans>=res){

        return;

    }

    if(!m)

    {

        if(ans<res)

        res=ans;

        return ;

    }

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

    {

        if(!use[i]&&w[i]<=m)

        {

            use[i]=;

            m-=w[i];

            ans++;

            dfs(x+);

            m+=w[i];

            use[i]=;

            ans--;

        }

    }

    return;

}

int main()

{

    scanf("%d%lld",&n,&m);

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

    scanf("%d",&w[i]);

    dfs();

    printf("%d\n",res);

    return ;

}

比较尴尬.....

用后缀和优化剪枝

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

long long  w[],last[];

int n,m;

int ans;

inline int read()

{

    int f=,x=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';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+;i<=n;i++)

    {

        if(ww+last[i]<m)return;

        if(ww+w[i]>m)continue;

        dfs(i,use+,ww+w[i]);

    }

    return;

}

int main()

{

    n=read();m=read();

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

    w[i]=read();

    sort(w+,w+n+,cmp);

    for(int i=n;i>=;i--)

    last[i]=last[i+]+w[i];

    ans=n;

    dfs(,,);

    printf("%d\n",ans);

    return ;

}

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

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

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

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

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

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

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

int ans(),w[],n;

long long mm;

map<int, int>m;

void dfs(int js,int last,int sum,bool k)

{

    int r=n;

    if(k){m[sum]=js;r/=;}

    else

    {

        if(m.find(mm - sum)!=m.end())

        ans=min(ans,js+m[mm-sum]);

    }

    for(int i=last;i<r;i++)

    dfs(js+,i+,sum+w[i],k);

}

int main()

{

    scanf("%d%lld",&n,&mm);

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

    scanf("%d",&w[i]);

    dfs(,,,true);

    dfs(,n/,,false);

    printf("%d\n",ans);

    return ;

}

巴特西

codevs 2144 砝码称重2

2144 砝码称重 2

最新文章

热门文章