//****************************************************************************80

void i4vec_sort_insert_d ( int n, int a[] )

//****************************************************************************80
//
//  Purpose:
//
//    i4vec_sort_insert_d() uses a descending insertion sort on an I4VEC.
//
//  Discussion:
//
//    An I4VEC is a vector of I4's.
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    13 April 1999
//
//  Author:
//
//    John Burkardt
//
//  Reference:
//
//    Donald Kreher, Douglas Simpson,
//    Algorithm 1.1,
//    Combinatorial Algorithms,
//    CRC Press, 1998, page 11.
//
//  Input:
//
//    Input, int N, the number of items in the vector.
//    N must be positive.
//
//    int A[N]: data to be sorted.
//
//  Output:
//
//    int A[N]: the sorted data.
//
{
  int i;
  int j;
  int x;

  for ( i = 1; i < n; i++ )
  {
    x = a[i];
    j = i;

    while ( 1 <= j && a[j-1] < x )
    {
      a[j] = a[j-1];
      j = j - 1;
    }
    a[j] = x;
  }

  return;
}
//****************************************************************************80

int subset_sum_swap ( int n, int a[], int sum_desired, int index[] )

//****************************************************************************80
// 
//  Purpose:
//
//    subset_sum_swap() seeks a solution of the subset sum problem by swapping.
// 
//  Discussion:
// 
//    Given a collection of N not necessarily distinct positive integers A(I),
//    and a positive integer SUM_DESIRED, select a subset of the values so that
//    their sum is as close as possible to SUM_DESIRED without exceeding it.
// 
//  Algorithm:
// 
//    Start with no values selected, and SUM_ACHIEVED = 0.
// 
//    Consider each element A(I):
// 
//      If A(I) is not selected and SUM_ACHIEVED + A(I) <= SUM_DESIRED,
//        select A(I).
// 
//      If A(I) is still not selected, and there is a selected A(J)
//      such that SUM_GOT < SUM_ACHIEVED + A(I) - A(J),
//        select A(I) and deselect A(J).
// 
//      If no items were selected on this sweep,
//        exit.
//      Otherwise,
//        repeat the search.
// 
//  Licensing:
// 
//    This code is distributed under the MIT license.
// 
//  Modified:
// 
//    25 July 2011
// 
//  Author:
// 
//    John Burkardt
// 
//  Reference:
// 
//    Donald Kreher, Douglas Simpson,
//    Combinatorial Algorithms,
//    CRC Press, 1998,
//    ISBN: 0-8493-3988-X,
//    LC: QA164.K73.
// 
//  Input:
// 
//    int N, the number of values.  N must be positive.
// 
//    int A[N], a collection of positive values.
// 
//    int SUM_DESIRED, the desired sum.
// 
//  Output:
//
//    int A[N]: A has been sorted into descending order.
// 
//    int INDEX[N]; INDEX(I) is 1 if A(I) is part of the
//    sum, and 0 otherwise.
// 
//    int SUBSET_SUM_SWAP, the sum of the selected elements.
// 
{
  int i;
  int j;
  int nmove;
  int sum_achieved;
// 
//  Initialize.
// 
  sum_achieved = 0;

  for ( i = 0; i < n; i++ )
  {
    index[i] = 0;
  }
// 
//  Sort into descending order.
// 
  i4vec_sort_insert_d ( n, a );

  for ( ; ; )
  {
    nmove = 0;

    for ( i = 0; i < n; i++ )
    {
      if ( index[i] == 0 )
      {
        if ( sum_achieved + a[i] <= sum_desired )
        {
          index[i] = 1;
          sum_achieved = sum_achieved + a[i];
          nmove = nmove + 1;
          continue;
        }
      }

      if ( index[i] == 0 )
      {
        for ( j = 0; j < n; j++ )
        {
          if ( index[j] == 1 )
          {
            if ( sum_achieved < sum_achieved + a[i] - a[j] &&
              sum_achieved + a[i] - a[j] <= sum_desired )
            {
              index[j] = 0;
              index[i] = 1;
              nmove = nmove + 2;
              sum_achieved = sum_achieved + a[i] - a[j];
              break;
            }
          }
        }
      }
    }
    if ( nmove <= 0 )
    {
      break;
    }
  }

  return sum_achieved;
}