第2题:石子划分(每空4分,共16分)
给出n堆石子,以及每堆石子数。请将它们分为两堆,使得这两堆的总石子数差最小。输入n,以及每堆石子数,输出分为两堆后的最小差值。比如,n=4,四堆石子分别有13,6,8,14颗,则可以分为13+8和14+6的两堆,它们的最小差为1。
以下程序:(1)求得所有石子数total,以及它的一半half;
(2)在所有石子堆中作适当选择,对每种选择方案,求不超过half的已选中堆中的石子总数的最大值max。所求即为(total-max)-max。
(3)以a[j]表示第j堆石子数;以b[j]表示第j堆石子是否被选中,如果b[j]=1,表示第j堆被选中,如果b[j]=0表示第j堆没有被选中。
(4)各种方案的表达及次序如下:以00…00(均不选中),00..01(只选中第n堆石子),00..10(只选中第n-1堆石子),00…11(选中第n-1堆和第n堆石子),00…100(选中第n-2堆石子),00…101(选中第n-2堆和第n堆石子),11…11(选中所有n堆石子)。
请完善该程序。
program xx07_6;
const maxn=20;
var n,i,j:longint;
total,half,sum,max:longint;
a:array[1..maxn] of longint;
b:array[0..maxn]of 0..1;
begin
readln(n);
total:=0;
for i:=1 to n do begin
read(a[i]);
total:=total+a[i];
end;
half:=total div 2;
max:=0;
for i:=1 to n do b[i]:=0;
i:=n;
while i>0 do begin
sum:=0;
for j:=1 to n do
sum:=______sum+a[j]*b[j]_______;
if ________(sum<=half) and (sum>max)_________ then
max:=sum;
i:=n;
while (i>0) and (b[i]=1) do
i:=___i-1____;
if i>0 then begin
b[i]:=____1____;
for j:=i+1 to n do b[j]:=0;
end;
end;
writeln(total-max-max);
end.