使用贪心算法解决条件排序问题

Question

给定k个排好序的序列s1，s2,s3,…sk,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并2个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序，使所需的总的比较次数最少。

Answer 1

我的思路是：
1，按序列的项函数Len(I)对序列s进行排序，
2，依次对排序后的序列的1，2，项3，4，项，进行合并，这样，如果是奇数项的话，将不用对项数最大的序列进行合并，从而符合贪心算法的局部最优性质。
3，循环第二步。直到得到一个序列。

Answer 2

用JAVA还可以试一下，DELPHI对偶就有难度了。

Answer 3

问题解决了，方式有两种；上面的思路是其一；
另外一种实现更简单的方式是：
依次对归并排序后序列的相邻两项S1-S2->S12, S3-S4->S34…对得到的结果集再次排序后继续按照这种方式归并S12-S34->S1234, S56-S78->S5678…并排序得到的结果集。直到得到一个完全排序的序列S123…k.这样在对奇数个数序列进行归并操作时，将不用对项数最大的序列归并从而符合贪心算法的局部最优性质。算法代码如下。
  Function OrderMerger:integer;
var i,k,Aord, sum,Temp: integer;  // k为结果数据项数，Aord为奇偶性，sum存放比较次数
    begin
      try
        Sum := 0;   //初始化控制变量和存放结果变量值
        Aord := length(len) mod 2;
        k := (length(len) + Aord) div 2;        while( k > 1) do
        begin
          for i:= 0 to (k -Aord) - 1 do  //合并s[2i],s[2i+1]
          begin
            Len[i] := Len[2*i] + Len[2*i+1] ; //计算所需比较次数
            sum := sum + Len[i] -1 ;
          end;
      //如果aord =1，将剩余的一位没有归并的项下移，并对得到的结果序列进行再次排序
          if Aord = 1 then
          begin
            Len[k-1] := Len[2*(k-1)];            if Len[k-2] > len[k-1] then
            begin
              Temp := Len[k-1];
              for I := k-2 downto 0 do
              begin
                if Len[i] > temp then
                begin
                  Len[i+1] := Len[i];
                  Len[i] := Temp;
                end
                else begin
                  len[i+1] := temp;
                  break;
                end;
              end;
            end;
          end;          Aord := k mod 2;      //赋值控制变量K，Aord
          k := (k+Aord) div 2;
        end;
        Result := sum + Len[0] + Len[1] -1;
      except
        result := -1;
      end;
end;

Answer 4

对排序后的序列S，首先归并项数最小的两个序列S1-S2->S12,对得到的中间结果集合S12,S3,…Sk进行排序；然后依次归并S12-S3->S123…循环执行k-1次归并操作，直至得到一个序列S12…k.。算法代码如下：
Function GreedMerger:integer;
var I,j,k,sum,Count, temp: integer;
Begin
Try
  k := strtoint(Edit1.Text);
  count := 0;  //记录当前第一个序列的项数
  sum := 0;  for i:= 1 to k-1 do
  begin
    Count := Count + OrderLen[i];
    Sum := Sum + count -1;
    //排序中间结果集和    
if (I< (k-1)) and (count > orderLen[i+1]) then
    begin
      Temp := orderLen[i+1];
      orderLen[i+1] := count;
      count := Temp;
      for j := i+1 to k-2 do
      begin
        if OrderLen[j] > OrderLen[j+1] then
        begin
          Temp := orderLen[j+1];
          orderLen[j+1] := orderLen[j];
          orderLen[j] := Temp;
        end
        else break;
      end;
  end;
  result := sum;
except 
  result := -1;
       end;  
End;