一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过1，且两个组内的所有人体重加起来尽可能地接近
input:
输入数据的第1行是一个n，表示参加拔河比赛的总人数，n<=100，接下来的n行表示第1到第n个人的体重，每个人的体重都是整数（1<=weight<=450）。
output:
输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。
input:
3
100
90
200
output:
190 200
分析：
这道题目不满足动态规划最优子结构的特性。因为最优子结构要求一个问题的最优解只取决于其子问题的最优解。就这道题目而言，当前n-1个人的分组方案达到最优时，并不意味着前n个人的分组方案也最优。但题目中标注出每个人的最大体重为450，这就提醒我们可以从这里做文章，否则的话，命题者大可把最大体重标注到长整型。假设w[i]表示第i个人的体重。c[i,j,k]表示在前i个人中选j个人在一组，他们的重量之和等于k是否可能。显然，c[i,j,k]是boolean型，其值为true代表有可能，false代表没有可能。那c[i,j,k]与什么有关呢？从前i个人中选出j个人的方案，不外乎两种情况：⑴第i个人没有被选中，此时就和从前面i-1个人中选出j个人的方案没区别，所以c[i,j,k]与c[i-1,j,k]有关。⑵第i个人被选中，则c[i,j,k]与c[i-1,j-1,k-w[i]]有关。综上所述，可以得出：c[i,j,k]=c[i-1,j,k] or c[i-1,j-1,k-w[i]]。
这道题占用的空间看似达到三维，但因为i只与i-1有关，所以在具体实现的时候，可以把第一维省略掉。另外在操作的时候，要注意控制j与k的范围（0<=j<=i/2，0<=k<=j*450），否则有可能超时。
这种方法的实质是把解本身当作状态的一个参量，把最优解问题转化为判定性问题，用递推的方法求解。这种问题有一个比较明显的特征，就是问题的解被限定在一个较小的范围内，如这题中人的重量不超过450。
【参考程序】：
var bo:array[0..100,0..45000]of boolean;
w:array[1..100]of longint;
n,n2,i,j,k,sum,ans,min:longint;
begin
//while not eof do
//begin
read(n);
n2:=(n+1) div 2;//最大能选的人数
sum:=0;
for i:=1 to n do
begin
read(w[i]);
inc(sum,w[i]);
end;
fillchar(bo,sizeof(bo),false);
bo[0,0]:=true;
for i:=1 to n do//先进行装箱看n2个人所能产生的结果
for j:=n2-1 downto 0 do
for k:=450*i downto 0 do
bo[j+1,k+w[i]]:=bo[j+1,k+w[i]] or bo[j,k];
ans:=0;min:=maxlongint;
for k:=0 to 450*n2 do
if bo[n2,k] then
if abs(sum-k-k)<min then
begin//n2个结果里面选择最接近0的那么另一边即为最优
min:=abs(sum-k-k);
if k<=sum div 2 then ans:=k
else ans:=sum-k;
end;
writeln(ans,' ',sum-ans);
//end;
end.