program main

!*****************************************************************************80
!
!! change_dynamic_test() tests change_dynamic().
!
!  Licensing:
!
!    This code is distributed under the MIT license. 
!
!  Modified:
!
!    20 August 2014
!
!  Author:
!
!    John Burkardt
!
  implicit none

  call timestamp ( )
  write ( *, '(a)' ) ''
  write ( *, '(a)' ) 'change_dynamic_test():'
  write ( *, '(a)' ) '  Fortran90 version'
  write ( *, '(a)' ) '  Test change_dynamic().'

  call change_dynamic_test01 ( )
  call change_dynamic_test02 ( )
!
!  Terminate.
!
  write ( *, '(a)' ) ''
  write ( *, '(a)' ) 'change_dynamic_test():'
  write ( *, '(a)' ) '  Normal end of execution.'
  write ( *, '(a)' ) ''
  call timestamp ( )

  stop 0
end
subroutine change_dynamic_test01 ( )

!*****************************************************************************80
!
!! change_dynamic_test01() lists the problem data.
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    19 August 2014
!
!  Author:
!
!    John Burkardt
!
  implicit none

  integer, parameter :: coin_value_list_num = 33
  integer, parameter :: test_num = 7

  integer coin_num
  integer, dimension ( test_num ) :: coin_num_list = (/ &
    3, &
    5, &
    6, &
    7, &
    3, &
    6, &
    3 /)
  integer coin_offset
  integer, dimension ( test_num ) :: coin_offset_list = (/ &
     1, &
     4, &
     9, &
    15, &
    22, &
    25, &
    31 /)
  integer, allocatable :: coin_value(:)
  integer, dimension ( coin_value_list_num ) :: coin_value_list = (/ &
     5,  9, 13, &
     1,  4,  5,  8, 11, &
     1,  5, 10, 25, 50, 100, &
     1,  2,  6, 12, 24,  48,  60, &
     1,  3,  4, &
    16, 17, 23, 24, 39,  40, &
     6,  9, 20 /)
  integer i
  integer target
  integer, dimension ( test_num ) :: target_list = (/ &
    19, &
    29, &
    96, &
    96, &
     6, &
   100, &
    43 /)
  integer test

  write ( *, '(a)' ) ''
  write ( *, '(a)' ) 'change_dynamic_test01():'
  write ( *, '(a)' ) '  List the problem data.'

  do test = 1, test_num

    coin_num = coin_num_list(test)
    coin_offset = coin_offset_list(test)
    allocate ( coin_value(1:coin_num) )
    coin_value(1:coin_num) = coin_value_list(coin_offset:coin_offset+coin_num-1)
    target = target_list(test)

    write ( *, '(a)' ) ''
    write ( *, '(a,i1,a)' ) '  Test ', test, ':'
    write ( *, '(a,i4)' ) '  Number of coins = ', coin_num
    write ( *, '(a)' ) '  Values = '
    do i = 1, coin_num
      write ( *, '(2x,i4)' ) coin_value(i)
    end do
    write ( *, '(a)' ) ''
    write ( *, '(a,i4)' ) '  Target = ', target

    deallocate ( coin_value )

  end do

  return
end
subroutine change_dynamic_test02 ( )

!*****************************************************************************80
!
!! change_dynamic_test02() tests change_dynamic().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    20 August 2014
!
!  Author:
!
!    John Burkardt
!
  implicit none

  integer, parameter :: coin_value_list_num = 33
  integer, parameter :: test_num = 7

  integer, allocatable :: a(:)
  integer coin_num
  integer, dimension ( test_num ) :: coin_num_list = (/ &
    3, &
    5, &
    6, &
    7, &
    3, &
    6, &
    3 /)
  integer coin_offset
  integer, dimension ( test_num ) :: coin_offset_list = (/ &
     1, &
     4, &
     9, &
    15, &
    22, &
    25, &
    31 /)
  integer, allocatable :: coin_value(:)
  integer, dimension ( coin_value_list_num ) :: coin_value_list = (/ &
     5,  9, 13, &
     1,  4,  5,  8, 11, &
     1,  5, 10, 25, 50, 100, &
     1,  2,  6, 12, 24,  48,  60, &
     1,  3,  4, &
    16, 17, 23, 24, 39,  40, &
     6,  9, 20 /)
  integer i
  integer, parameter :: i4_huge = 2147483647
  integer target
  integer, dimension ( test_num ) :: target_list = (/ &
    19, &
    29, &
    96, &
    96, &
     6, &
   100, &
    43 /)
  integer test

  write ( *, '(a)' ) ''
  write ( *, '(a)' ) 'change_dynamic_test02():'
  write ( *, '(a)' ) '  change_dynamic() computes A(T), the smallest number'
  write ( *, '(a)' ) '  of coins needed to form a given sum T, by computing'
  write ( *, '(a)' ) '  the list A(0) through A(T).'

  do test = 1, test_num

    coin_num = coin_num_list(test)
    coin_offset = coin_offset_list(test)
    allocate ( coin_value(1:coin_num) )
    coin_value(1:coin_num) = coin_value_list(coin_offset:coin_offset+coin_num-1)
    target = target_list(test)

    write ( *, '(a)' ) ''
    write ( *, '(a,i1,a)' ) '  Test ', test, ':'
    write ( *, '(a,i4)' ) '  Number of coins = ', coin_num
    write ( *, '(a)' ) '  Values = '
    do i = 1, coin_num
      write ( *, '(2x,i4)' ) coin_value(i)
    end do
    write ( *, '(a)' ) ''
    write ( *, '(a,i4)' ) '  Target = ', target

    allocate ( a(0:target) )

    call change_dynamic ( coin_num, coin_value, target, a )

    write ( *, '(a)' ) ''
    do i = 0, target
      if ( a(i) == i4_huge ) then
        write ( *, '(2x,i4,a)' ) i, '  Not possible!'
      else
        write ( *, '(2x,i4,2x,i4)' ) i, a(i)
      end if
    end do

    deallocate ( a )
    deallocate ( coin_value )

  end do


  return
end