subroutine i4_to_digits_binary ( i, n, c )

!*****************************************************************************80
!
!! i4_to_digits_binary() produces the binary digits of an I4.
!
!  Discussion:
!
!    An I4 is an integer.
!
!  Example:
!
!     I    N     C               Binary
!    --  ---   ---         ------------
!     0    1   0                      0
!     0    2   0, 0                  00
!     1    3   1, 0, 0              100
!     2    3   0, 1, 0              010
!     3    3   1, 1, 0              011
!     4    3   0, 0, 1              100
!     8    3   0, 0, 0           (1)000
!     8    5   0, 0, 0, 1, 0      01000
!    -8    5   0, 0, 0, 1, 0  (-) 01000
!
!     0    3   0, 0, 0
!     1    3   1, 0, 0
!     2    3   0, 1, 0
!     3    3   1, 1, 0
!     4    3   0, 0, 1
!     5    3   1, 0, 1
!     6    3   0, 1, 1
!     7    3   1, 1, 1
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    09 December 2010
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer I, an integer to be represented.
!
!    Input, integer N, the number of binary digits to produce.
!
!    Output, integer C(N), the first N binary digits of I,
!    with C(1) being the units digit.
!
  implicit none

  integer n

  integer c(n)
  integer i
  integer i_copy
  integer j

  i_copy = abs ( i )

  do j = 1, n

    c(j) = mod ( i_copy, 2 )
    i_copy = i_copy / 2

  end do

  return
end
subroutine subset_sum_count ( n, w, t, ind_min, ind_max, solution_num )

!*****************************************************************************80
!
!! subset_sum_count() counts solutions to the subset sum problem in a range.
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    09 December 2010
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer N, the size of the set.
!
!    Input, integer W(N), a set of weights.  The length of this
!    array must be no more than 31.
!
!    Input, integer T, the target value.
!
!    Input, integer IND_MIN, IND_MAX, the lower and upper
!    limits to be searched.  0 <= IND_MIN <= IND_MAX <= (2^N)-1.
!
!    Output, integer SOLUTION_NUM, the number of distinct
!    solutions of the subset sum problem found within the given range.
!
  implicit none

  integer n

  integer c(n)
  integer ind
  integer ind_max
  integer ind_max2
  integer ind_min
  integer ind_min2
  integer solution_num
  integer t
  integer w(n)
!
!  Check the data.
!
  if ( n < 1 ) then
    write ( *, '(a)' ) ' '
    write ( *, '(a)' ) 'SUBSET_SUM_COUNT - Fatal error!'
    write ( *, '(a)' ) '  N < 1.'
    stop
  end if

  if ( 31 < n ) then
    write ( *, '(a)' ) ' '
    write ( *, '(a)' ) 'SUBSET_SUM_COUNT - Fatal error!'
    write ( *, '(a)' ) '  31 < N.'
    stop
  end if

  ind_min2 = max ( ind_min, 0 )
  ind_max2 = min ( ind_max, ( 2 ** n ) - 1 )
!
!  Run through the range.
!
  write ( *, '(a)' ) ' '
  write ( *, '(a,i8)' ) '  Searching from IND_MIN = ', ind_min2
  write ( *, '(a,i8)' ) '  through IND_MAX = ', ind_max2

  solution_num = 0

  do ind = ind_min2, ind_max2
!
!  Convert INDEX into vector of indices in W.
!
    call i4_to_digits_binary ( ind, n, c )
!
!  If the sum of those weights matches the target, return combination.
!
    if ( dot_product ( c, w ) == t ) then
      solution_num = solution_num + 1
    end if

  end do

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

!*****************************************************************************80
!
!! subset_sum_count_test() tests subset_sum_count().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    10 November 2015
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer N, the number of weights.
!
!    Input, integer W(N), a set of weights.  The length of this
!    array must be no more than 31.
!
!    Input, integer T, the target value.
!
!    Input, integer IND_MIN, IND_MAX, the lower and upper
!    limits to be searched.
!
  implicit none

  integer n

  integer i
  integer ind_max
  integer ind_min
  integer solution_num
  integer t
  integer w(n)

  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'SUBSET_SUM_COUNT_TEST:'
  write ( *, '(a)' ) '  SUBSET_SUM_COUNT_TEST counts solutions'
  write ( *, '(a)' ) '  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
subroutine subset_sum_count_tests ( )

!*****************************************************************************80
!
!! subset_sum_count_tests() tests subset_sum_count_test().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    10 November 2015
!
!  Author:
!
!    John Burkardt
!
  implicit none

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

  call timestamp ( )
  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'subset_sum_count_tests():'
  write ( *, '(a)' ) '  subset_sum_count_test() calls SUBSET_SUM_COUNT with'
  write ( *, '(a)' ) '  a particular set of problem data.'
!
!  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 subset_sum_count_test ( n, w, t, ind_min, ind_max )

    deallocate ( w )

  end do

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

!*****************************************************************************80
!
!! subset_sum_find() seeks a subset of a set that has a given sum.
!
!  Discussion:
!
!    This function tries to compute a target value as the sum of
!    a selected subset of a given set of weights.
!
!    This function works by brute force, that is, it tries every
!    possible subset to see if it sums to the desired value.
!
!    Given N weights, every possible selection can be described by
!    one of the N-digit binary numbers from 0 to 2^N-1.
!
!    This function includes a range, which allows the user to
!    control which subsets are to be checked.  Thus, if there are
!    N weights, specifying a range of [ 0, 2^N-1] indicates that
!    all subsets should be checked.  On the other hand, this full
!    range could be broken down into smaller subranges, each of
!    which could be checked independently.
!
!    It is possible that, in the given range, there may be multiple
!    solutions of the problem.  This function will only return
!    one such solution, if found.  However, the function may be called
!    again, with an appropriate restriction of the range, to continue
!    the search for other solutions.
!
!  Example:
!
!    w = [ 1, 2, 4, 8, 16, 32 ];
!    t = 22;
!    r = [ 0, 2^6 - 1 ];
!
!    call subset_sum_find ( w, t, r, c, ind )
!
!    c = [ 2, 3, 5 ]
!    index = 22
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    09 December 2010
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer N, the size of the set.
!
!    Input, integer W(N), a set of weights.  The length of this
!    array must be no more than 31.
!
!    Input, integer T, the target value.
!
!    Input, integer IND_MIN, IND_MAX, the lower and upper
!    limits to be searched.  0 <= IND_MIN <= IND_MAX <= (2^N)-1.
!
!    Output, integer IND, the index of the solution.
!    If IND is -1, no solution was found in the range.
!
!    Output, integer C(N), indicates the solution, assuming
!    that IND is not -1.  In that case, the sum T is made by selecting
!    those weights W(I) for which C(I) is 1.  In fact,
!    T = sum ( 1 <= I <= N ) C(I) * W(I).
!
  implicit none

  integer n

  integer c(n)
  integer ind
  integer ind_max
  integer ind_max2
  integer ind_min
  integer ind_min2
  integer t
  integer w(n)
!
!  Check the data.
!
  if ( n < 1 ) then
    write ( *, '(a)' ) ' '
    write ( *, '(a)' ) 'SUBSET_SUM_FIND - Fatal error!'
    write ( *, '(a)' ) '  N < 1.'
    stop
  end if

  if ( 31 < n ) then
    write ( *, '(a)' ) ' '
    write ( *, '(a)' ) 'SUBSET_SUM_FIND - Fatal error!'
    write ( *, '(a)' ) '  31 < N.'
    stop
  end if

  ind_min2 = max ( ind_min, 0 )
  ind_max2 = min ( ind_max, ( 2 ** n ) - 1 )
!
!  Run through the range.
!
  write ( *, '(a)' ) ' '
  write ( *, '(a,i8)' ) '  Searching from IND_MIN = ', ind_min2
  write ( *, '(a,i8)' ) '  through IND_MAX = ', ind_max2

  do ind = ind_min2, ind_max2
!
!  Convert INDEX into vector of indices in W.
!
    call i4_to_digits_binary ( ind, n, c )
!
!  If the sum of those weights matches the target, return combination.
!
    if ( dot_product ( c, w ) == t ) then
      return
    end if

  end do

  ind = - 1

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

!*****************************************************************************80
!
!! subset_sum_find_test() tests subset_sum_find().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    10 November 2015
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer N, the number of weights.
!
!    Input, integer W(N), a set of weights.  The length of this
!    array must be no more than 31.
!
!    Input, integer T, the target value.
!
!    Input, integer IND_MIN, IND_MAX, the lower and upper
!    limits to be searched.
!
!    Output, integer IND, the index of a solution, if found,
!    or the value -1 otherwise.
!
  implicit none

  integer n

  integer c(n)
  integer i
  integer ind
  integer ind_max
  integer ind_min
  integer t
  integer w(n)

  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'SUBSET_SUM_FIND_TEST:'
  write ( *, '(a)' ) '  SUBSET_SUM_FIND seeks 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 subset_sum_find_tests ( )

!*****************************************************************************80
!
!! subset_sum_find_tests() tests subset_sum_find_test().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    18 May 2012
!
!  Author:
!
!    John Burkardt
!
  implicit none

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

  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'SUBSET_SUM_FIND_TESTS:'
  write ( *, '(a)' ) '  SUBSET_SUM_FIND_TEST calls SUBSET_SUM_FIND with'
  write ( *, '(a)' ) '  a particular set of problem data.'
!
!  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 subset_sum_find_test ( n, w, t, ind_min, ind_max, ind )

    deallocate ( w )

  end do

  return
end
subroutine subset_sum_table ( t, n, w, table )

!*****************************************************************************80
!
!! subset_sum_table() sets a subset sum table.
!
!  Discussion:
!
!    The subset sum problem seeks to construct the value T by summing a 
!    subset of the values W.
!
!    This function seeks a solution by constructing a table TABLE of length T,
!    so that TABLE(I) = J means that the sum I can be constructed, and that
!    the last member of the sum is an entry of W equal to J.
!
!  Example:
!
!    w = [ 1, 2, 4, 8, 16, 32 ];
!    t = 22;
!
!    table = subset_sum ( w, t, r )
!    table = [ 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 
!      16, 16, 16, 16, 16, 16, 16 ]
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    09 November 2015
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer T, the target value.
!
!    Input, integer N, the number of weights.
!
!    Input, integer W(N), the weights.
!
!    Output, integer TABLE(T), the subset sum table.  TABLE(I) is 
!    0 if the target value I cannot be formed.  It is J if the value I can 
!    be formed, with the last term in the sum being the value J.
!
  implicit none

  integer n
  integer t

  integer i
  integer j
  integer table(t)
  integer w(n)

  table(1:t) = 0

  do i = 1, n
    do j = t - w(i), 0, -1

      if ( j == 0 ) then
        if ( table(w(i)) == 0 ) then
          table(w(i)) = w(i)
        end if
      else if ( table(j) /= 0 .and. table(j+w(i)) == 0 ) then
        table(j+w(i)) = w(i)
      end if

    end do

  end do
  
  return
end
subroutine subset_sum_table_test ( t, n, w )

!*****************************************************************************80
!
!! subset_sum_table_test() tests subset_sum_table().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    10 November 2015
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer T, the target value.
!
!    Input, integer N, the number of weights.
!
!    Input, integer W(N), a set of weights.
!
  implicit none

  integer n
  integer t

  integer i
  integer list(t)
  integer m
  integer table(t)
  integer w(n)

  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'SUBSET_SUM_TABLE_TEST:'
  write ( *, '(a)' ) '  SUBSET_SUM_TABLE seeks 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_table ( t, n, w, table )

  write ( *, '(a)' ) ''

  if ( table(t) == 0 ) then
    write ( *, '(a)' ) '  No solution was found.'
  else
    call subset_sum_table_to_list ( t, table, m, list )
    write ( *, '(i8)', advance = 'no' ) t
    write ( *, '(a)', advance = 'no' ) ' = '
    do i = 1, m
      if ( 1 < i ) then
        write ( *, '(a)', advance = 'no' ) ' + '
      end if
      write ( *, '(i8)', advance = 'no' ) list(i)
    end do
    write ( *, '(a)' ) ''
  end if

  return
end
subroutine subset_sum_table_tests ( )

!*****************************************************************************80
!
!! subset_sum_table_tests() tests subset_sum_table_test().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    10 November 2015
!
!  Author:
!
!    John Burkardt
!
  implicit none

  integer n
  integer t
  integer test
  integer, parameter :: test_num = 7
  integer, allocatable :: w(:)

  write ( *, '(a)' ) ' '
  write ( *, '(a)' ) 'SUBSET_SUM_TABLE_TESTS:'
  write ( *, '(a)' ) '  SUBSET_SUM_TABLE_TEST calls SUBSET_SUM_TABLE with'
  write ( *, '(a)' ) '  a particular set of problem data.'
!
!  Find individual solutions.
!
  do test = 1, test_num

    if ( test == 1 ) then
      t = 53
      n = 8
      allocate ( w(1:n) )
      w = (/ 15, 22, 14, 26, 32, 9, 16, 8 /)
    else if ( test == 2 ) then
      t = 5842
      n = 10
      allocate ( w(1:n) )
      w = (/ 267,  493,  869,  961, 1000, 1153, 1246, 1598, 1766, 1922 /)
    else if ( test == 3 ) then
      t = 2463098
      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 /)
    else if ( test == 4 ) then
      t = 50
      n = 10
      allocate ( w(1:n) )
      w = (/ 41, 34, 21, 20,  8,  7,  7,  4,  3,  3 /)
    else if ( test == 5 ) then
      t = 100
      n = 9
      allocate ( w(1:n) )
      w = (/ 81, 80, 43, 40, 30, 26, 12, 11, 9 /)
    else if ( test == 6 ) then
      t = 22
      n = 6
      allocate ( w(1:n) )
      w = (/ 1, 2, 4, 8, 16, 32 /)
    else if ( test == 7 ) then
      t = 50
      n = 10
      allocate ( w(1:n) )
      w = (/ 25, 27, 3, 12, 6, 15, 9, 30, 21, 19 /)
    end if

    call subset_sum_table_test ( t, n, w )

    deallocate ( w )

  end do

  return
end
subroutine subset_sum_table_to_list ( t, table, m, list )

!*****************************************************************************80
!
!! subset_sum_table_to_list() converts a subset sum table to a list.
!
!  Discussion:
!
!    The subset sum problem seeks to construct the value T by summing a 
!    subset of the values W.
!
!    This function takes a table computed by subset_sum_table() and converts
!    it to the corresponding list of values that form the sum.
!
!  Example:
!
!    t = 22
!    n = 6
!    w = [ 1, 2, 4, 8, 16, 32 ]
!    call subset_sum ( t, n, w, table )
!    table = [ 1, 2, 2, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8, 8, 
!      16, 16, 16, 16, 16, 16, 16 ]
!
!    call subset_sum_table_to_list ( t, table, m, list )
!    m = 3
!    list = [ 2, 4, 16 ]
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    10 November 2015
!
!  Author:
!
!    John Burkardt
!
!  Parameters:
!
!    Input, integer T, the target value.
!
!    Input, integer TABLE(T), the subset sum table.
!
!    Output, integer M, the number of items in the list.
!    If M == 0, then no solution was found and the list is empty.
!
!    Output, integer LIST(T), contains the M items in the
!    list of weights that sum to T.
!    
  implicit none

  integer t

  integer i
  integer list(t)
  integer m
  integer table(t)

  list(1:t) = 0

  i = t
  m = 0
  do while ( 0 < i )
    m = m + 1
    list(m) = table(i)
    i = i - table(i)
  end do

  return
end
subroutine timestamp ( )

!*****************************************************************************80
!
!! timestamp() prints the current YMDHMS date as a time stamp.
!
!  Example:
!
!    31 May 2001   9:45:54.872 AM
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    18 May 2013
!
!  Author:
!
!    John Burkardt
!
  implicit none

  character ( len = 8 ) ampm
  integer d
  integer h
  integer m
  integer mm
  character ( len = 9 ), parameter, dimension(12) :: month = (/ &
    'January  ', 'February ', 'March    ', 'April    ', &
    'May      ', 'June     ', 'July     ', 'August   ', &
    'September', 'October  ', 'November ', 'December ' /)
  integer n
  integer s
  integer values(8)
  integer y

  call date_and_time ( values = values )

  y = values(1)
  m = values(2)
  d = values(3)
  h = values(5)
  n = values(6)
  s = values(7)
  mm = values(8)

  if ( h < 12 ) then
    ampm = 'AM'
  else if ( h == 12 ) then
    if ( n == 0 .and. s == 0 ) then
      ampm = 'Noon'
    else
      ampm = 'PM'
    end if
  else
    h = h - 12
    if ( h < 12 ) then
      ampm = 'PM'
    else if ( h == 12 ) then
      if ( n == 0 .and. s == 0 ) then
        ampm = 'Midnight'
      else
        ampm = 'AM'
      end if
    end if
  end if

  write ( *, '(i2,1x,a,1x,i4,2x,i2,a1,i2.2,a1,i2.2,a1,i3.3,1x,a)' ) &
    d, trim ( month(m) ), y, h, ':', n, ':', s, '.', mm, trim ( ampm )

  return
end