不是VIP会员,不能显示答案

题目解答

题目:
第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.
考点:
分析:
解答:
评论:
老师: