Codevs No.2144 砝码称重2

2016-05-31 22:01:16

题目链接: 砝码称重2 (Codevs No.2144)

题目大意:

　　给定N个砝码,求称出M的重量所需砝码最小个数

解法:

　　贪心

　　使砝码数量最小,当然是每个砝码越大越好

　　首先排序,从大砝码开始试,遇到的第一个解一定最优

需要注意的地方:

　　1.这道题的数据还是很给力的,裸贪心过不了,要加一个前缀和判断可达性进行优化

 1 //砝码称重2 (Codevs No.2144)
 2 //贪心
 3 #include<stdio.h>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=35;
 7 long long N,M;
 8 int ans;
 9 int tmp;
10 long long a[maxn];
11 long long sum[maxn];
12 bool DFS(int x,long long val,int step)
13 {
14     if(val==0)
15     {
16         ans=step;
17         return 1;
18     }
19     for(int i=x;i>=1;i--)
20     {
21         if(val-sum[i]>0)break;
22         if(val-a[i]>=0)
23         {
24             tmp=DFS(i-1,val-a[i],step+1);
25             if(tmp)return 1;
26         }
27     }
28     return 0;
29 }
30 int main()
31 {
32     scanf("%d %lld",&N,&M);
33     for(int i=1;i<=N;i++)
34     {
35         scanf("%lld",&a[i]);
36     }
37     sort(a+1,a+N+1);
38     for(int i=1;i<=N;i++)
39     {
40         sum[i]=sum[i-1]+a[i];
41     }
42     DFS(N,M,0);
43     printf("%d",ans);
44 }