function x = partition_greedy ( w )

%*****************************************************************************80
%
%% partition_greedy() approaches the partition problem using a greedy algorithm.
%
%  Discussion:
%
%    We are given a set of N integers W.
%
%    We seek to partition W into subsets such that the subsets
%    have sums that are equal, or else as nearly equal as possible.
%
%    The "discrepancy" is the absolute value of the difference between the
%    two sums, and will be zero if we have solved the problem.
%
%    For a given set of integers, there may be zero, one, or many solutions.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    16 October 2022
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer W(N), the integers.
%
%  Output:
%
%    integer X(N), indicates the proposed solution.
%    X(I) is 0 for items in set 0 and 1 for items in set 1.
%
  n = length ( w );

  [ w2, index ] = sort ( w, 'descend' );
  x = zeros ( n, 1 );

  s0_sum = 0.0;
  s1_sum = 0.0;
  for i = 1 : n
    j = index(i);
    if ( s0_sum < s1_sum )
      x(j) = 0;
      s0_sum = s0_sum + w(j);
    else
      x(j) = 1;
      s1_sum = s1_sum + w(j);
    end
  end

  return
end
 
