题意：
在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n 个人作为陪审团的候选人，然后再从这n 个人中选m 人组成陪审团。选m 人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0 到20。为了公平起见，法官选出陪审团的原则是：选出的m 个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。1<=n<=200, 1<=m<=20 ,m<=n.
分析：
本题不存在多项式时间可解的算法，属于NP问题。排列组合的暴力算法能体会到200！的勘比指数级别复杂度的恐怖性，显然是不可以的。题目中要求的是最优值，因此可以根据有限的状态(-20*20 ——20*20)，大大减少解空间。动态规划的前提是前一阶段的各项最优结果作为后一阶段的子结构具有无后效性（最优化原理与无后效性，这是原理和前提，递归式的正确性），并且在前一阶段结果在后一阶段之前都已经计算(这涉及实际编程中的要点，很多出错是由于弄错多层循环的顺序导致前一阶段结果未完全计算)。动态规划通过最优结果来进行后续计算，极大地减少了搜索空间，类比于搜索算法以及应用（比如回溯）中常用的剪枝技巧。
递归式有常见的套路，但是如果对比其他相应问题及其递归式的同时，从问题的本质分析，会达到事半功倍的效果。最优的情况有很多种，首先考虑如何无后效性。如果每个物品依次放入（像背包问题的放法），则不能固定当前最优解中物品的个数。因此考虑组合中物品的个数作为归纳元素，即一批批放。当前结构是组合中有i个物品的各状态最优解集合，则下一个阶段对每一个最优子状态和每个物品两两组合，求得多一个元素后的组合最优值。
要求绝对值最小，但是动态规划不支持绝对值之间的优化，因此去绝对值处理，在输出结果时考虑正负情况即可。由于存在负数，而各组合的差作为数组坐标，因此加上固定的常数使之变为正数即可(加上20*20)，在差值相同时求"和最大"的情况，也就是各个状态(差值)下的最优解。放入物品后物品的差值使整体的差值增加，同时总个数加1，新的状态（第 i +1 次递归时差值）根据上一个状态（第 i 次递归时的差值）得到，如果这时的状态对应的总分和能达到最优，即将此作为最优值。递归方案为：可行方案f(j-1, x)能演化成方案f(j, k)的必要条件是：存在某个候选人i，i 在方案f(j-1, x)中没有被选上，且x+V(i) = k。在所有满足该必要条件的f(j-1, x)中，选出 f(j-1, x) + S(i) 的值最大的那个，那么方案f(j-1, x)再加上候选人i，就演变成了方案 f(j, k)。
考虑到同一状态有多种情况最优值相同的情况，此种情况下的状态不是最优值状态，因此不考虑。例如，用数字表示各个物品的总分差，1与5，2与4，都能使和达到6，两者相同，任意取1即可。因为此时存在1+2为最优（总分差最小优先考虑）。一般地，如果两者和相同（由于多于1个物品，因此都能拆成2部分的和，看成4个物品，如果只有一个物品，那两个物品没有区别，如果最优组合同时包括两者，先选和后选是等价的），a+b = c+d ，且a = min(a,b),，c= min(c,d)，则若 “ a < b 且 c<d”或者“a < b 且 c = d” 或者" a = b 且 c < d"，可以找到 a+c 为满足条件的方案，若"a =b 且 c = d"，则 "a = b = c = d"，则考虑各个物品总分和的情况。类似地，例如，用数字表示各个物品的总分和，1与5，2与4，都能使和达到6，两者相同，任意取1即可。因为此时存在1+2为最优（总分差最小优先考虑）。一般地，如果两者和相同，a+b = c+d ，且a = min(a,b),，c= min(c,d)，则若 “ a < b 且 c<d”或者“a < b 且 c = d” 或者" a = b 且 c < d"，可以找到 a+c 为满足条件的方案，其他可能性不为最优值，引出矛盾，若"a =b 且 c = d"，则 "a = b = c = d"，等价于4个相同的物品。在4个物品中如果有最优方案同时包括了多于2个物品的情况，那么此处任选2种，之后再添4个中另外的物品，不影响最终的结果。这里是4个组合看成物品，如果细化到具体的物品，则按照上述原理继续根据差与和讨论即可。
此题也可以与背包问题相联系，差值可以看成背包的当前容量值，和可以看成背包的价值，在相同容量时使价值最大。区别是，背包问题是指装最大价值的物品，因此在各个当前容量中找最大价值即可，而本题是满足容量与某一中心（就是为了避免负数而加的常数）最靠近，在最靠近时价值最大的解，并且解中物品的个数是确定的，因此这个变形的背包不能用原始背包的方法解。
处理时涉及到的状态只与前一个状态有关，因此可以用状态压缩，即只用2个数组，用于轮换，轮换存储当前状态与前一个状态。
本题需要输出各个物品并且验证是否物品已经包括，因此采用路径数组保存。s = path[i][j]表示在第 i 次递归时，差值为 j 时对应选的物品，它的前一个物品即第 i-1 次递归时的物品根据path[i-1][j-dec[s]]得出，其中dec[s]表示第s种物品对应的总分差，这样逆推到之前的状态。这里n = 200,如果n < 33，则可以用int的位（1与0）来模拟是否取到，对应的操作时与、或、1的左移的操作，效率较高。
测试实例：
1）几组一般数据，用于查看算法中有没有编写时写错变量等初级问题或者是算法的严重错误。（用于编程后）
2）边界数据。n= 200,m = 200,m=n时的必要组合，用于检查数组越界问题以及各个极限情况。（用于编程前、后）
3）关键数据。针对算法的选择是否正确，比如贪心法解决的问题由于算法的选择错误使之在很多关键数据中出现错误。根据易错点选择某种变量和相等之类的特例，事先仔细考虑关键数据就可以正确选择算法。（用于编程前、后）
调试过程：
由于太久没有做题了，各种低级错误，但是要积累教训。
1）数组的范围改变时漏了改相应的地方。每修改一步时要考虑对整个程序的影响。
2）初始条件谨慎处理。比如dp[0][baseline]赋值为0，其余的赋值为-1，如果都是0就不能区分是否已经放了物品（因为有差为0的）。这类错误只要找一个特例和一个通用例子，并且一定要耐心手工带入一组数据就可以发现。检查各个变量是否在每次循环中正确初始化与赋值。
3）调试时不要盲目改，要确定是否是错了，或者是由于别的原因错了，静心不要太心急。
4）不要因为主观意念而疏忽。一开始我没有看清n的范围，在存储路径时用了位运算以为提高了速度一直沉浸在得意之中以致于最后才发现这个错误，导致调试了很久。信念很重要，很多情况觉得太复杂，不想去证明，干脆在OJ上碰运气，这在做了很多题后可以有这个经验，这是以前训练准备比赛时的心态。但现在需要分析，毕竟是解决问题不能碰运气。首先相信能证明，总比懒地动好，不行的话再找资料，但不能直接看题解。
5）细致地分析，一步步调试，先把最能做到的做掉，如果优化有点困难，则先把未优化的调试出来，一口气写完最后错哪都很难找。
6）最后看题解找错误原因时，不要看别人的代码。如果思路是对的，那就是细节处理问题了。如果还没找到错误原因，粗略地看代码，看大致架构是否正确。接下来范围很小，真的是自己可以检查的小错误了，根据和参考代码实现细节不同的地方体会自己做的疏漏。最后可以看参考代码在哪些地方比自己的代码优化。
7）写完自己的代码后，再看看别人的代码是否有优化。
只要静下心来想，仔细，严谨，一道题的收获不仅仅是一个算法，更重要的是思维模式。
1
#include<iostream>
2#include<string>
3#include<algorithm>
4usingnamespace std;
5#define clr(a,b) memset(a,b,sizeof(a))
6#define baseline 410
7#define INF 999999
8int main()
9
{
10
//freopen("out.txt","w",stdout);
11 int dec[210]; //每个物品的两党差
12 int sum[210]; //每个物品的两党和
13 int dp[2][820];//各个“差之和”对应的最大"和之和"
14 int visit[2][820];//最优值时选用的物品
15 int element[2][40010];//每次循环后的dp非零项编号
16 int path[21][820]; //存储存放物品集合的路径中当前元素
17 int count=0,i,j,s,n,m,cur,k,e_tail,t1,t2;
18 while(scanf("%d%d",&n,&m) && (m+n))
19
{
20 printf("Jury #%d\n",++count);
21 //clr(dec,0);
22 //clr(sum,0);
23 clr(dp,-1); //清成-1，0可以这么写，但是1就不行了。0对应二进制全0，-1对应二进制全1。
24 clr(visit,0);
25 clr(element,0);
26 clr(path[m-1],-1);
27 //input
28 for(i = 0; i < n; i++)
29 {
30 int a,b;
31 scanf("%d%d",&a,&b);
32 dec[i] = a-b;
33 sum[i] = a+b;
34
}
35 //sort?不用，和顺序无关
36 //dp
37 //element[0][0]= 0; //都未放时只可能是“不放”这一种可能,因此存储相应的坐标0
38 dp[0][baseline] = 0;
39 //visit[0][baseline] = 0;
40 e_tail = 1;
41 for(i = 0; i < m; i++)//依次放入m批物品
42 {
43 if(i%2 == 0)//在偶数次时，参考数组为0，处理存储数组为1，轮换数组
44 cur = 0;
45 else cur = 1;
46 clr(dp[1-cur],-1);
47 clr(element[1-cur],0);
48 clr(visit[1-cur],0);
49 int e_tail_temp = 0;
50
51 for(j = 0;j< e_tail; j++)//内层这两个循环的嵌套顺序没有关系，由于遍历时产生新状态的顺序无关。
52 {
53 k = element[cur][j]+baseline;
54 for(s = 0; s< n; s++)//n个候选物品
55 {
56
57 if(dp[1-cur][k+dec[s]]==-1)//即第i件物品的循环中未处理过
58 {
59 //if(visit[cur][k]& (1 << s))//即该物品之前已经包括过//天啊，s的范围是200不是20啊
60 //continue;
61 t1 = i-1; //以下检验s是否已经包含
62 t2 =k;
63 while (t1>=0 && path[t1][t2]!=s)
64 {
65 t2-= dec[path[t1][t2]];
66 t1--;
67 }
68 if (t1>=0)
69 continue;
70 dp[1-cur][k+ dec[s]] = dp[cur][k] + sum[s];
71 element[1-cur][e_tail_temp++] =element[cur][j]+ dec[s];
72 //visit[1-cur][k+dec[s]] = visit[cur][k]|(1 << s );
73 path[i][k+ dec[s]] = s;
74 }
75 elseif((dp[cur][k] + sum[s])>(dp[1-cur][k+ dec[s]]))
76 {
77 //if(visit[cur][k]&(1 << s))//即该物品之前已经包括过
78 //continue;
79 t1 = i-1; //以下检验s是否已经包含
80 t2 =k;
81 while (t1>=0 && path[t1][t2]!=s)
82 {
83 t2-= dec[path[t1][t2]];
84 t1--;
85 }
86 if (t1>=0)
87 continue;
88 dp[1-cur][k+ dec[s]] = dp[cur][k] + sum[s];
89 //visit[1-cur][k+dec[s]] = visit[cur][k]| (1 << s);
90 path[i][k+ dec[s]] = s;
91 }
92 }
93 }
94 e_tail = e_tail_temp;
95 }
96
97
98 //output
99 int target,ans = INF;
100 for(i = 0; i < e_tail; i++)
101 {
102
103
104 if(element[1-cur][i] >= 0)
105 k = element[1-cur][i];
106 else
107 k =-element[1-cur][i];
108 if(k <ans)
109 {
110 ans = k;
111 target = i;
112 }
113 elseif(k == ans &&dp[1-cur][element[1-cur][target]+ baseline] < dp[1-cur][element[1-cur][i]+baseline])
114 target = i;
115
116 }
117 int pro,def;
118 pro =(dp[1-cur][element[1-cur][target] + baseline] + element[1-cur][target])/2;
119 def =(dp[1-cur][element[1-cur][target] + baseline] - element[1-cur][target])/2;
120 printf("Best jury has value %d for prosecution and value %dfor defence:\n",pro,def);
121 /**//*k = visit[1-cur][element[1-cur][target] + baseline];
122 for(i = 0; i< n;i++)
123 {
124 if(k & 1)
125 printf("%d",i+1);
126 k >>=1;
127 }*/
128 int num[21];
129 k =element[1-cur][target] + baseline;
130 for(i = m-1; i >= 0; i--)
131 {
132 j = path[i][k];
133 num[m-i-1] = j;
134 k -= dec[j];
135 }
136 sort(num,num+m);
137 for(i = 0;i < m; i++)
138 printf(" %d",num[i]+1);
139 printf("\n\n");
140
141 }
142
143