主题：谁能帮我？——石子归并问题
ltf
[专家分：0] 发布于 2005-07-25 16:11:00
[em18]
问题叙述：
你有一堆石头质量分别为W1,W2,W3...WN.(W＜＝100000)现在需要你将石头合并为两堆，使两堆质量的差为最小。
输入：
该程序有多组测试数据，每组测试数据第一行为整数N（1<=N<=20），表示有N堆石子。接下去N行，为每堆石子的质量。
输出：
每组测试数据只需输出合并后两堆的质量差的最小值。
例：
输入
5
5
8
13
27
14
2
4
4
输出
3
0
欢迎高手解答，不胜荣幸，谢谢！
回复列表 （共8个回复）
沙发
MK [专家分：110] 发布于 2005-07-25 19:56:00
program tju1017;
var a : array[0..20]of longint;
n, a1, a2, i : integer;
procedure sort;
var flag : boolean;
j : integer;
begin
flag:=true;
for i:=1 to n-1 do
begin
for j:=1 to n-i do
if a[j]<a[j+1] then
begin
a[0]:=a[j+1]; a[j+1]:=a[j]; a[j]:=a[0];
flag:=false;
end;
if flag then exit;
end;
end;
begin
repeat
readln(n);
for i:=1 to n do readln(a[i]);
if n=1 then writeln(a[1]);
if n=2 then writeln(abs(a[1]-a[2]));
if (n<>1)and(n<>2) then
begin
sort; a1:=a[1]; a2:=a[2];
for i:=3 to n do
if a1>a2 then a2:=a[i]+a2 else a1:=a[i]+a1;
writeln(abs(a1-a2));
end;
until seekeof;
end.
板凳
MK [专家分：110] 发布于 2005-07-25 19:57:00
不知道是否正确，没有在tju上试过。
3 楼
sd5774188 [专家分：260] 发布于 2005-07-25 21:15:00
我过了的程序（搜索）；
program yb(input,output);
const max=20;
var z:array[1..max]of longint;
n,i:longint;
best:longint;
procedure search(step,bb:longint);
begin
if step=n+1 then begin if abs(bb)<best then best:=abs(bb);exit;end;
search(step+1,bb+z[step]);
search(step+1,bb-z[step]);
end;
begin
while not seekeof(input) do
begin
read(n);
for i:=1 to n do
read(z[i]);
best:=maxlongint;
search(1,0);
writeln(best);
end;
end.
4 楼
mlj [专家分：310] 发布于 2005-07-26 12:13:00
用动态规划好多了
5 楼
口口and枕头 [专家分：1550] 发布于 2005-07-26 18:01:00
请问tju是什么?
6 楼
delphi6 [专家分：3450] 发布于 2005-07-26 19:55:00
[img]http://bbs.cqreview.com/UploadFile/2005-7/2005712154831382.gif[/img]
7 楼
我笨故我在 [专家分：0] 发布于 2005-07-29 14:17:00
tju------http://acm.tongji.edu.cn/problem.php
8 楼
mlj [专家分：310] 发布于 2005-07-29 16:25:00
不要拿我东西再着刷!
我来回复
您所在位置：