poj 3628
1
#include <iostream>
2
#include <algorithm>
3
#define MAXN_COWS 25
4
#define MAX_NUM 123456789
5
using namespace std;
6
7
int _m[MAXN_COWS];
8
int _min;
9
int num_cows;
10
int len_bookshelf;
11
void dfs(int time,int sum);
12
int main()
13

{
14
freopen("acm.acm","r",stdin);
15
int i;
16
_min = MAX_NUM;
17
cin>>num_cows;
18
cin>>len_bookshelf;
19
for(i = 0; i < num_cows; ++ i)
20
{
21
cin>>_m[i];
22
}
23
dfs(0,0);
24
cout<<_min - len_bookshelf<<endl;
25
}
26
27
void dfs(int time,int sum)
28

{
29
if(time == num_cows)
30
{
31
if(sum < len_bookshelf)
32
{
33
return;
34
}
35
else
36
{
37
if(sum < _min)
38
{
39
_min = sum;
40
}
41
return;
42
}
43
}
44
45
sum += _m[time];
46
dfs(time+1,sum);
47
sum -= _m[time];
48
dfs(time+1,sum);
49
return;
50
}

2

3

4

5

6

7

8

9

10

11

12

13



14

15

16

17

18

19

20



21

22

23

24

25

26

27

28



29

30



31

32



33

34

35

36



37

38



39

40

41

42

43

44

45

46

47

48

49

50
