#! /usr/bin/env python3
#
def knapsack_random_test ( ):

#*****************************************************************************80
#
## knapsack_random_test() tests knapsack_random().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    14 April 2025
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'knapsack_random_test():' )
  print ( '  python version: ' + platform.python_version ( ) )
  print ( '  numpy version:  ' + np.version.version )
  print ( '  Test knapsack_random()' )

  knapsack_random_test01 ( )
#
#  Terminate.
#
  print ( '' )
  print ( 'knapsack_random_test():' )
  print ( '  Normal end of execution.' )
  return

def knapsack_random_test01 ( ):

#*****************************************************************************80
#
## knapsack_random_test01() tests knapsack_random().
#
#  Discussion:
#
#    In the 0/1 knapsack problem, a knapsack of capacity C is given,
#    as well as N items, with the I-th item of weight W(I).
#
#    A selection is "acceptable" if the total weight is no greater than C.
#
#    It is desired to find an optimal acceptable selection, that is,
#    an acceptable selection such that there is no acceptable selection
#    of greater weight.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    14 April 2025
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'knapsack_random_test01():' )
  print ( '  knapsack_random() random selects a subset of n items' )
  print ( '  and considers it as a solution to a knapsack problem.' )
  print ( '  Maximize profit without exceeding weight limit.' )

  W = 170
  n = 7
  v = np.array ( [  442, 525, 511, 593, 546, 564, 617 ], dtype = float )
  w = np.array ( [   41,  50,  49,  59,  55,  57,  60 ], dtype = float )

  print ( '' )
  print ( '  Weight limit is ', W )
  print ( '  Number of items is ', n )
  print ( '  Number of subsets is ', 2**n )
  print ( '  Value array ', v )
  print ( '  Weight array ', w )

  for test in range ( 0, 10 ):
#
#  Take items in random order, skipping items that would exceed the weight limit.
#
    c_test = np.zeros ( n, dtype = int )
    perm = np.random.permutation ( n )
    w_test = 0.0
    for i in perm:
      if ( w_test + w[i] < W ):
        c_test[i] = 1
        w_test = w_test + w[i]
      
    v_test = np.dot ( c_test, v )
    w_test = np.dot ( c_test, w )
    if ( 0.0 < w_test ):
      r_test = v_test / w_test
    else:
      r_test = 0.0

    print ( '' )
    print ( '  Selected items:', c_test )
    if ( W < w_test ):
      print ( '  Weight ', w_test, ' exceeds weight limit ', W )
    else:
      print ( '  Weight ', w_test )
      print ( '  Value ', v_test )
      print ( '  Ratio ', r_test )

  return

def timestamp ( ):

#*****************************************************************************80
#
## timestamp() prints the date as a timestamp.
#
#  Licensing:
#
#    This code is distributed under the MIT license. 
#
#  Modified:
#
#    06 April 2013
#
#  Author:
#
#    John Burkardt
#
  import time

  t = time.time ( )
  print ( time.ctime ( t ) )

  return None

if ( __name__ == '__main__' ):
  timestamp ( )
  knapsack_random_test ( )
  timestamp ( )