1 #include<iostream>
2 #include<algorithm>
3 #define MAXN 201
4 #define count C_ount
5 using namespace std;
6
7 int _m[
20][
801];
8 int count[
20][
801];
9 int a[
20];
10
11 struct _node
12 {
13 int first;
14 int second;
15 };
16
17 _node _cand[MAXN];
18 int n;
19 int main()
20 {
21 //freopen("acm.acm","r",stdin);
22 int m;
23 int i;
24 int j;
25 int time;
26 int max;
27 int u;
28 int v;
29 int u_v;
30 int _i;
31 int _j;
32 int _test_time =
0;
33 int index;
34 int ans;
35 while(cin>>n>>m,n||
m)
36 {
37 memset(count,-
1,
sizeof(count));
38 memset(_m,-
1,
sizeof(_m));
39 max = m*
20;
40 for(i =
0; i < n; ++
i)
41 {
42 cin>>u>>
v;
43 _cand[i].first = u -
v;
44 _cand[i].second = u +
v;
45 }
46 for(i =
0; i < n; ++
i)
47 {
48 if(count[
0][max+_cand[i].first] <
_cand[i].second)
49 {
50 _m[
0][max+_cand[i].first] =
i;
51 count[
0][max+_cand[i].first] =
_cand[i].second;
52 }
53 }
54 for(time =
0; time < m-
1; ++
time)
55 {
56 for(u_v =
0; u_v <= max*
2; ++
u_v)
57 {
58 if(_m[time][u_v] != -
1)
59 {
60 for(i =
0; i < n; ++
i)
61 {
62 if(count[time+
1][u_v + _cand[i].first] < count[time][u_v] +
_cand[i].second)
63 {
64 _j =
u_v;
65 for(_i = time; _i >=
0; --
_i)
66 {
67 if(_m[_i][_j] ==
i)
68 break;
69 _j -=
_cand[_m[_i][_j]].first;
70 }
71 if(_i <
0)
72 {
73 _m[time+
1][u_v+_cand[i].first] =
i;
74 count[time+
1][u_v+_cand[i].first] = count[time][u_v] +
_cand[i].second;
75 }
76 }
77 }
78 }
79 }
80 }
81
82 /
83
84 for(i =
0; i <= max; ++
i)
85 {
86 int tem_1 = count[m-
1][max+
i];
87 int tem_2 = count[m-
1][max-
i];
88 if( (tem_1 = count[m-
1][max+i]) >=
0 || (tem_2 = count[m-
1][max-i]) >=
0)
89 {
90 if(tem_1 >
tem_2)
91 {
92 ans = max+
i;
93 }
94 else
95 {
96 ans = max-
i;
97 }
98 break;
99 }
100 }
101 cout<<
"Jury #"<<++ _test_time<<
endl;
102 cout<<
"Best jury has value "<<(count[m-
1][ans] + (ans - max))/
2<<
" for prosecution and value "<<(count[m-
1][ans] - (ans - max))/
2<<
" for defence:"<<
endl;
103 j =
ans;
104 index =
0;
105 for(i = m-
1; i >=
0; --
i)
106 {
107 a[index ++] =
_m[i][j];
108 j -=
_cand[_m[i][j]].first;
109 }
110 sort(a,a+
index);
111 for(i =
0; i < index; ++
i)
112 {
113 cout<<
" "<<a[i]+
1;
114 }
115 cout<<
endl;
116 cout<<
endl;
117 }
118 }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com
转载于:https://www.cnblogs.com/gavinsp/p/4563208.html
相关资源：垃圾分类数据集及代码
