# include <stdlib.h>

# include "subset_sum_swap.h"

/******************************************************************************/

void i4vec_sort_insert_d ( int n, int a[] )

/******************************************************************************/
/*
  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:

    25 July 2010

  Author:

    John Burkardt

  Reference:

    Donald Kreher, Douglas Simpson,
    Algorithm 1.1,
    Combinatorial Algorithms,
    CRC Press, 1998, page 11.

  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;
}
/******************************************************************************/

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

/******************************************************************************/
/*
  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;
}