subroutine i4vec_sort_insert_d ( n, a )

c*********************************************************************72
c
cc i4vec_sort_insert_d() uses a descending insertion sort on an I4VEC.
c
c  Discussion:
c
c    An I4VEC is a vector of I4's.
c
c  Licensing:
c
c    This code is distributed under the MIT license.
c
c  Modified:
c
c    01 September 2008
c
c  Author:
c
c    John Burkardt
c
c  Reference:
c
c    Donald Kreher, Douglas Simpson,
c    Algorithm 1.1,
c    Combinatorial Algorithms,
c    CRC Press, 1998, page 11.
c
c  Input:
c
c    integer N, the number of items in the vector.
c    N must be positive.
c
c    integer A(N): data to be sorted.
c
c  Output:
c
c    integer A(N): the sorted data.
c
      implicit none

      integer n

      integer a(n)
      integer i
      integer j
      integer x

      do i = 2, n

        x = a(i)

        j = i - 1

10      continue

        if ( 1 .le. j ) then

          if ( x .le. a(j) ) then
            go to 20
          end if

          a(j+1) = a(j)
          j = j - 1
          go to 10

        end if

20      continue

        a(j+1) = x

      end do

      return
      end
      subroutine subset_sum_swap ( n, a, sum_desired, index, 
     &  sum_achieved )

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

      integer n

      integer a(n)
      integer i
      integer index(n)
      integer j
      integer nmove
      integer sum_achieved
      integer sum_desired
c
c  Initialize.
c
      sum_achieved = 0

      do i = 1, n
        index(i) = 0
      end do
c
c  Sort into descending order.
c
      call i4vec_sort_insert_d ( n, a )

10    continue

        nmove = 0

        do i = 1, n

          if ( index(i) .eq. 0 ) then

            if ( sum_achieved + a(i) .le. sum_desired ) then
              index(i) = 1
              sum_achieved = sum_achieved + a(i)
              nmove = nmove + 1
              go to 30
            end if

          end if

          if ( index(i) .eq. 0 ) then

            do j = 1, n

              if ( index(j) .eq. 1 ) then

                if ( sum_achieved .lt. sum_achieved + a(i) - a(j) .and.
     &            sum_achieved + a(i) - a(j) .le. sum_desired ) then
                  index(j) = 0
                  index(i) = 1
                  nmove = nmove + 2
                  sum_achieved = sum_achieved + a(i) - a(j)
                  go to 20
                end if

              end if

            end do

20          continue

          end if

30        continue

        end do

        if ( nmove .le. 0 ) then
          go to 40
        end if

      go to 10

40    continue

      return
      end