pascal问题 分石堆

来源：百度知道 编辑：UC知道 时间：2024/06/17 05:16:53
分石碓
有2n个石子，分别重W1,W2,……,W2n。现要将这些石子分成两堆，每堆n个石子，使得两堆石子的总重量之差最小。输出这个最小的“差”的绝对值。
输入格式
第一行一个整数n （1<=n<=13）。
此后的2n行，每行一个整数。第i行的整数Wi，表示第i个石子的重量（1<=Wi<=1000000）。
输出格式
仅一行，一个整数，表示两堆石子总重量差的最小值。
样例输入
3
5
5
8
13
27
14

样例输出
2
（一堆是：5 5 27；另一堆是：8 13 14）

我觉得用回溯，看下我程序哪里错了？
var
a,b:array[1..1000]of longint;
c,n,i,h:longint;

procedure sh(k:longint);
var
s,s1:longint;
begin
if k=n+1 then
begin
for i:=1 to n do
s:=b[i]+s; s1:=h-s;
if abs(s1-s)<c then c:=abs(s1-s);
end
else begin
for i:=k+1 to 2*n do
begin
b[k+1]:=a[i];
sh(k+1)
end;
end;
end;

begin
c:=maxlongint;
readln(n);
for i:=1 to 2*n do
begin
readln(a[i]);
h:=h+a[i];
end;
b[1]:=a[1];
sh(1);
writeln(c);
end.

其实回溯没必要这么复杂
像下面这样就可以了
(每块石头只有两种可能 在第一堆或者在第二堆
k代表第k块石头 sum代表第一堆的总和[第二堆就是全部石头的和减去第一堆])
我很不明白上面程序中
for i:=k+1 to 2*n do
begin
b[k+1]:=a[i];
sh(k+1)
end;
是什么意思
而且过程中的变量初始值不是0 上面程序s,s1都应该赋值为0
且在过程用的变量应该在过程中声明
上面程序的过程里应该声明i为integer

var a:array[1..1000]of longint;
c,n,i,h:longint;

procedure sh(k:longint;sum:longint);
begin
if k>=2*n+1 then begin
if abs(h-sum-sum)<c then c:=abs(h-sum-sum);
exit;
end
else begin
sh(k+1,sum+a[k]);
sh(k+1,sum);
end;
end;

begin
c:=maxlongint;
readln(n);
for i:=1 to 2*n do begin readln(a[i]);h:=h+a[i]; end;

sh(1,0);
writeln(c);
end.