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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

#define maxn 31

int n,ans=0x7fffffff;

long long a[maxn],s[maxn],m;

bool cmp(int x,int y){return x>y;}

long long qread(){

    long long i=;

    char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}

    return i;

}

void dfs(int pos,int cnt,long long sum){

    if(sum==m){ans=min(ans,cnt);return;}

    if(cnt>=ans)return;

    if(pos>n)return;

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

        if(s[i]<m-sum)return;

        if(a[i]>m-sum)continue;

        dfs(i+,cnt+,sum+a[i]);

    }

}

int main(){

    freopen("Cola.txt","r",stdin);

    scanf("%d",&n);

    m=qread();

    for(int i=;i<=n;i++)a[i]=qread();

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

    for(int i=n;i>=;i--)s[i]=s[i+]+a[i];

    dfs(,,);

    printf("%d",ans);

}

100分后缀和+剪枝

#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 ;

}

100分 meet in the middle

巴特西

Codevs 2144 砝码称重 2

2144 砝码称重 2

最新文章

热门文章