1
#include<stdio.h>
2#include<string.h>
3int n,m;
4int a[10],b[10];
5int max=9999;
6int hash[10];
7void dfs(int x,int y)
8
{
9
int i;
10 if(x>n)
11
{
12 return;
13
}
14 if(y<=0)
15 {
16 if(max>x)
17 {
18 max=x;
19 }
20 return;
21 }
22
23 for(i=0;i<n;i++)
24 {
25 if(hash[i])
26 {
27 hash[i]=0;
28 if(y<=b[i])
29 {
30 dfs(x+1,y-2*a[i]);
31
32 }else
33 {
34 dfs(x+1,y-a[i]);
35 }
36 hash[i]=1;
37 }
38 }
39 return;
40
}
41int main()
42{
43 int i,j,k,l;
44 while(scanf("%d%d",&n,&m)!=EOF)
45 {
46 for(i=0;i<n;i++)
47 {
48 scanf("%d%d",&a[i],&b[i]);
49 }
50 memset(hash,1,sizeof(hash));
51 max=9999;
52 dfs(0,m);
53 if(max!=9999)
54 printf("%d\n",max);
55 else
56 puts("-1");
57 }
58}
posted on 2009-01-27 14:06
混沌的云 阅读(172)
评论(0) 编辑 收藏 引用