program main

!*****************************************************************************80
!
!! MAIN is the main program for SUBSET_SUM_PRB.
!
!  Licensing:
!
!    This code is distributed under the GNU LGPL license.
!
!  Modified:
!
!    18 May 2012
!
!  Author:
!
!    John Burkardt
!
  implicit none

  integer ( kind = 4 ) ind
  integer ( kind = 4 ) ind_max
  integer ( kind = 4 ) ind_min
  integer ( kind = 4 ) n
  integer ( kind = 4 ) t
  integer ( kind = 4 ) test
  integer ( kind = 4 ), parameter :: test_num = 9
  integer ( kind = 4 ), allocatable :: w(:)

  call timestamp ( )
  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'SUBSET_SUM_TEST:'
  write ( *, '(a)' ) '  FORTRAN90 version'
  write ( *, '(a)' ) '  Test the SUBSET_SUM library.'
!
!  Find individual solutions.
!
  do test = 1, test_num

    if ( test == 1 ) then
      n = 8
      allocate ( w(1:n) )
      w = (/ 15, 22, 14, 26, 32, 9, 16, 8 /)
      t = 53
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 2 ) then
      n = 8
      allocate ( w(1:n) )
      w = (/ 15, 22, 14, 26, 32, 9, 16, 8 /)
      t = 53
      ind_min = ind + 1
      ind_max = 2**n - 1
    else if ( test == 3 ) then
      n = 8
      allocate ( w(1:n) )
      w = (/ 15, 22, 14, 26, 32, 9, 16, 8 /)
      t = 53
      ind_min = ind + 1
      ind_max = 2**n - 1
    else if ( test == 4 ) then
      n = 10
      allocate ( w(1:n) )
      w = (/ 267,  493,  869,  961, 1000, 1153, 1246, 1598, 1766, 1922 /)
      t = 5842
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 5 ) then
      n = 21
      allocate ( w(1:n) )
      w = (/  518533, 1037066, 2074132, 1648264, 796528, &
             1593056,  686112, 1372224,  244448, 488896, &
              977792, 1955584, 1411168,  322336, 644672, &
             1289344,   78688,  157376,  314752, 629504, &
             1259008 /)
      t = 2463098
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 6 ) then
      n = 10
      allocate ( w(1:n) )
      w = (/ 41, 34, 21, 20,  8,  7,  7,  4,  3,  3 /)
      t = 50
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 7 ) then
      n = 9
      allocate ( w(1:n) )
      w = (/ 81, 80, 43, 40, 30, 26, 12, 11, 9 /)
      t = 100
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 8 ) then
      n = 6
      allocate ( w(1:n) )
      w = (/ 1, 2, 4, 8, 16, 32 /)
      t = 22
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 9 ) then
      n = 10
      allocate ( w(1:n) )
      w = (/ 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 /)
      t = 50
      ind_min = 0
      ind_max = 2**n - 1
    end if

    call test01 ( n, w, t, ind_min, ind_max, ind )

    deallocate ( w )

  end do
!
!  Simply count solutions.
!
  do test = 1, test_num

    if ( test == 1 ) then
      n = 8
      allocate ( w(1:n) )
      w = (/ 15, 22, 14, 26, 32, 9, 16, 8 /)
      t = 53
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 2 ) then
      n = 8
      allocate ( w(1:n) )
      w = (/ 15, 22, 14, 26, 32, 9, 16, 8 /)
      t = 53
      ind_min = 68
      ind_max = 2**n - 1
    else if ( test == 3 ) then
      n = 8
      allocate ( w(1:n) )
      w = (/ 15, 22, 14, 26, 32, 9, 16, 8 /)
      t = 53
      ind_min = 167
      ind_max = 2**n - 1
    else if ( test == 4 ) then
      n = 10
      allocate ( w(1:n) )
      w = (/ 267,  493,  869,  961, 1000, 1153, 1246, 1598, 1766, 1922 /)
      t = 5842
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 5 ) then
      n = 21
      allocate ( w(1:n) )
      w = (/  518533, 1037066, 2074132, 1648264, 796528, &
             1593056,  686112, 1372224,  244448, 488896, &
              977792, 1955584, 1411168,  322336, 644672, &
             1289344,   78688,  157376,  314752, 629504, &
             1259008 /)
      t = 2463098
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 6 ) then
      n = 10
      allocate ( w(1:n) )
      w = (/ 41, 34, 21, 20,  8,  7,  7,  4,  3,  3 /)
      t = 50
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 7 ) then
      n = 9
      allocate ( w(1:n) )
      w = (/ 81, 80, 43, 40, 30, 26, 12, 11, 9 /)
      t = 100
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 8 ) then
      n = 6
      allocate ( w(1:n) )
      w = (/ 1, 2, 4, 8, 16, 32 /)
      t = 22
      ind_min = 0
      ind_max = 2**n - 1
    else if ( test == 9 ) then
      n = 10
      allocate ( w(1:n) )
      w = (/ 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 /)
      t = 50
      ind_min = 0
      ind_max = 2**n - 1
    end if

    call test02 ( n, w, t, ind_min, ind_max )

    deallocate ( w )

  end do
!
!  Terminate.
!
  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'SUBSET_SUM_TEST'
  write ( *, '(a)' ) '  Normal end of execution.'
  write ( *, '(a)' ) ' '
  call timestamp ( )

  return
end
subroutine test01 ( n, w, t, ind_min, ind_max, ind )

!*****************************************************************************80
!
!! TEST01 seeks a subset of a set that has a given sum.
!
!  Licensing:
!
!    This code is distributed under the GNU LGPL license.
!
!  Modified:
!
!    09 December 2010
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer ( kind = 4 ) N, the number of weights.
!
!    Input, integer ( kind = 4 ) W(N), a set of weights.  The length of this
!    array must be no more than 31.
!
!    Input, integer ( kind = 4 ) T, the target value.
!
!    Input, integer ( kind = 4 ) IND_MIN, IND_MAX, the lower and upper
!    limits to be searched.
!
!    Output, integer ( kind = 4 ) IND, the index of a solution, if found,
!    or the value -1 otherwise.
!
  implicit none

  integer ( kind = 4 ) n

  integer ( kind = 4 ) c(n)
  integer ( kind = 4 ) i
  integer ( kind = 4 ) ind
  integer ( kind = 4 ) ind_max
  integer ( kind = 4 ) ind_min
  integer ( kind = 4 ) t
  integer ( kind = 4 ) w(n)

  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'TEST01:'
  write ( *, '(a)' ) '  Seek a subset of W that sums to T.'
  write ( *, '(a)' ) ' '
  write ( *, '(a,i8)' ) '  Target value T = ', t
  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) '   I       W(I)'
  write ( *, '(a)' ) ' '
  do i = 1, n
    write ( *, '(2x,i2,2x,i8)' ) i, w(i)
  end do

  call subset_sum_find ( n, w, t, ind_min, ind_max, ind, c )

  if ( ind == -1 ) then
    write ( *, '(a)' ) ' '
    write ( *, '(a)' ) '  No solution was found.'
    return
  end if

  write ( *, '(a)' ) ' '
  write ( *, '(a,i8)' )  '  Solution index = ', ind
  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) '   I       W(I)  C(I)'
  write ( *, '(a)' ) ' '
  do i = 1, n
    write ( *, '(2x,i2,2x,i8,5x,i1)' ) i, w(i), c(i)
  end do

  return
end
subroutine test02 ( n, w, t, ind_min, ind_max )

!*****************************************************************************80
!
!! TEST02 counts solutions to the subset sum problem.
!
!  Licensing:
!
!    This code is distributed under the GNU LGPL license.
!
!  Modified:
!
!    09 December 2010
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer ( kind = 4 ) N, the number of weights.
!
!    Input, integer ( kind = 4 ) W(N), a set of weights.  The length of this
!    array must be no more than 31.
!
!    Input, integer ( kind = 4 ) T, the target value.
!
!    Input, integer ( kind = 4 ) IND_MIN, IND_MAX, the lower and upper
!    limits to be searched.
!
  implicit none

  integer ( kind = 4 ) n

  integer ( kind = 4 ) i
  integer ( kind = 4 ) ind_max
  integer ( kind = 4 ) ind_min
  integer ( kind = 4 ) solution_num
  integer ( kind = 4 ) t
  integer ( kind = 4 ) w(n)

  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'TEST02:'
  write ( *, '(a)' ) '  Count solutions to the subset sum problem.'
  write ( *, '(a)' ) ' '
  write ( *, '(a,i8)' ) '  Target value T = ', t
  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) '   I       W(I)'
  write ( *, '(a)' ) ' '
  do i = 1, n
    write ( *, '(2x,i2,2x,i8)' ) i, w(i)
  end do

  call subset_sum_count ( n, w, t, ind_min, ind_max, solution_num )

  write ( *, '(a)' ) ' '
  write ( *, '(a,i8)' ) '  Number of solutions = ', solution_num

  return
end