function [ a, indx ] = partition_greedy ( n, a )
%*****************************************************************************80
%
%% PARTITION_GREEDY attacks the partition problem with a greedy algorithm.
%
% Discussion:
%
% Given a collection of N not necessarily distinct positive integers A(I),
% it is desired to partition the values into two groups, whose sums are
% as close as possible.
%
% Algorithm:
%
% Begin with sets 1 and 2 empty.
%
% Process the data in descending order of magnitude.
%
% The next item A(I) is added to set 1 or set 2, whichever has the
% smallest current sum.
%
% Stop as soon as all items have been allocated.
%
% Licensing:
%
% This code is distributed under the GNU LGPL license.
%
% Modified:
%
% 26 January 2011
%
% Author:
%
% John Burkardt
%
% Reference:
%
% Brian Hayes,
% The Easiest Hard Problem,
% American Scientist,
% Volume 90, Number 2, March-April 2002, pages 113-117.
%
% Input:
%
% integer N, the number of values. N must be positive.
%
% integer A(N), a collection of positive values.
%
% Output:
%
% integer A(N), A has been sorted into descending order.
%
% integer INDX(N); INDX(I) is 1 if A(I) is part of
% set 1, and 2 if it is assigned to set 2.
%
sums(1:2) = 0;
a = i4vec_sort_insert_d ( n, a );
for i = 1 : n
if ( sums(1) < sums(2) )
j = 1;
else
j = 2;
end
indx(i) = j;
sums(j) = sums(j) + a(i);
end
return
end