Description
一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，要求两个组的人数相差不能超过
1，且两个组内的所有人体重加起来尽可能地接近。
Input
输入数据的第
1行是一个n，表示参加拔河比赛的总人数，n<=
100，接下来的n行表示第
1到第n个人的体重，每个人的体重都是整数（
1<=weight<=
450）。
Output
输出数据应该包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。
Sample Input
3
100
90
200
Sample Output
190 200
题解：这道题用dp，用max和min记录最大和最小的体重和,
if f[j,k]
then f[j+
1,k+a[i]]:=
true;
var a:
array[
0..
100]
of longint;
f:
array[
0..
50,
0..
45000]
of boolean;
i,k,n,j,sum,s,min1,max:longint;
function min(a,b:longint):longint;
begin
if b<a
then
begin
min:=b;
max:=a;
end else
begin
min:=a;
max:=b;
end;
end;
begin
readln(n);
for i:=
1 to n
do
begin
readln(a[i]);
sum:=sum+a[i];
end;
f[
0,
0]:=
true;
for i:=
1 to n
do
for j:=n
div 2 downto 0 do
for k:=sum
downto 0 do
if f[j,k]
then f[j+
1,k+a[i]]:=
true;
min1:=
50000;
for k:=
0 to sum
do
if f[n
div 2,k]
and (abs(k-sum+k)<min1)
then
begin
min1:=abs(k-sum+k);
s:=k;
end;
writeln(min(s,sum-s),
' ',max);
end.
转载请注明原文地址: https://ju.6miu.com/read-24489.html
