时间限制: 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
2
数据范围及提示 Data Size & Hint
1<=n<=30,1<=m<=2^31,1<=每个砝码的质量<=2^30
这个题,,
非常考研剪枝能力,
除了正常的最优性剪枝
还要用后缀和剪枝。
醉了醉了。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<map>
7 #define lli long long int
8 using namespace std;
9 void read(lli &n)
10 {
11 char c='+';lli x=0;bool flag=0;
12 while(c<'0'||c>'9')
13 {c=getchar();if(c=='-')flag=1;}
14 while(c>='0'&&c<='9')
15 {x=x*10+(c-48);c=getchar();}
16 flag==1?n=-x:n=x;
17 }
18 lli n,p;
19 lli a[10001];
20 lli sum2[10001];
21 map<int,bool>mp;
22 lli comp(lli a,lli b)
23 {
24 return a>b;
25 }
26 lli ans=0x7ffff;
27 void dfs(lli now,lli num,lli step,lli sum)
28 {
29
30 if(step>ans||sum>p)
31 return ;
32
33 if(sum==p)
34 {
35 ans=min(ans,step);
36 return ;
37 }
38 if(sum2[now]+sum<p)
39 return ;
40 if(now==n)
41 return ;
42 dfs(now+1,a[now+1],step+1,sum+a[now+1]);
43 dfs(now+1,num,step,sum);
44 }
45 int main()
46 {
47 read(n);read(p);
48 for(lli i=1;i<=n;i++)
49 read(a[i]);
50 sort(a+1,a+n+1,comp);
51 for(int i=n;i>=1;i--)
52 sum2[i]=sum2[i+1]+a[i];
53 for(lli i=1;i<=n;i++)
54 dfs(i,a[i],1,a[i]);
55 printf("%lld",ans);
56 return 0;
57 }