#! /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:
#
#    18 November 2015
#
#  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()' )

  subset_random_test ( )
  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:
#
#    13 November 2015
#
#  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 = 26
  n = 5
  v = np.array ( [  24,  13,  23,  15,  16 ] )
  w = np.array ( [  12,   7,  11,   8,   9 ] )

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

  for test in range ( 0, 10 ):

    c_test = knapsack_random ( n )
    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 knapsack_random ( n ):

#*****************************************************************************80
#
## knapsack_random() returns a random possible solution of a knapsack problem.
#
#  Discussion:
#
#    The subset is represented as a vector of binary digits.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    18 November 2024
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer n: the total number of items in the set.
#
#  Output:
#
#    integer c[n]: a subset.  Item i is in the subset if c[i] = 1.
#
  c = subset_random ( n )

  return c

def subset_random ( n ):

#*****************************************************************************80
#
## subset_random() returns a random subset of n items.
#
#  Discussion:
#
#    The subset is represented as a vector of binary digits.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    18 November 2024
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer n: the total number of items in the set.
#
#  Output:
#
#    integer c[n]: a subset.  Item i is in the subset if c[i] = 1.
#
  from numpy.random import default_rng

  rng = default_rng ( )

  c = rng.choice ( [ 0, 1 ], size = n )

  return c

def subset_random_test ( ):

#*****************************************************************************80
#
## subset_random_test() tests subset_random().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    18 November 2024
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  print ( '' )
  print ( 'subset_random_test():' )
  print ( '  Test subset_random()' )
  print ( '' )

  n = 5
  print ( '  Subsets will be of size n = ', n )
  print ( '' )

  for test in range ( 0, 10 ):
    c = subset_random ( n )
    index = subset_to_rank ( c )
    print ( index, ':', c )

  return

def subset_to_rank ( c ):

#*****************************************************************************80
#
## subset_to_rank() returns the rank of a subset().
#
#  Discussion:
#
#    The subset is described by a binary vector of n digits.
#    The units digit is the last one.
#    Reading from right to left, we add selected powers of 2.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    18 November 2024
#
#  Author:
#
#    John Burkardt
#
  n = len ( c )
  index = 0
  power2 = 1
  for i in range ( n - 1, -1, -1 ):
    index = index + c[i] * power2
    power2 = power2 * 2

  return index

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 ( )