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

#*****************************************************************************80
#
## knapsack_brute_test() tests knapsack_brute().
#
#  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_brute_test():' )
  print ( '  python version: ' + platform.python_version ( ) )
  print ( '  numpy version:  ' + np.version.version )
  print ( '  Test knapsack_brute()' )

  knapsack_brute_test01 ( )
#
#  Terminate.
#
  print ( '' )
  print ( 'knapsack_brute_test():' )
  print ( '  Normal end of execution.' )
  return

def knapsack_brute ( n, v, w, W ):

#*****************************************************************************80
#
## knapsack_brute() seeks a solution of the knapsack problem.
#
#  Discussion:
#
#    N valuable items are available, each with given value and weight.
#    A thief's knapsack can carry no more than W pounds.  The thief
#    seeks a selection of items to carry in the knapsack of maximum
#    total value.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    14 April 2025
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer n: the number of items.
#
#    real v[n], w[n]: the value and weight of each item.
#
#    real W: the maximum total weight capacity of the knapsack.
#
#  Output:
#
#    real vmax: the total value of the items in the knapsack.
#
#    real wmax: the total weight of the items in the knapsack.
#
#    integer cmax[n]: a vector of 0's and 1's, indicating which items
#    were selected.
#
  from itertools import combinations
  import numpy as np

  vmax = 0.0
  wmax = 0.0
  cmax = np.zeros ( n, dtype = int )

  c_test = np.zeros ( n, dtype = int )
  
  for r in range ( 0, n + 1 ):
    com = combinations ( np.arange ( n ), r )
    for combo in com:
      c_test = np.zeros ( n, dtype = int )
      for i in combo:
        c_test[i] = 1

      w_test = np.dot ( c_test, w )

      if ( w_test <= W ):
        v_test = np.dot ( c_test, v )

        if ( vmax < v_test ):
          cmax = c_test.copy()
          vmax = v_test
          wmax = w_test

      c_test = subset_next ( c_test )
      if ( sum ( c_test ) == 0 ):
        break

  return vmax, wmax, cmax

def knapsack_brute_test01 ( ):

#*****************************************************************************80
#
## knapsack_brute_test01() tests knapsack_brute().
#
#  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_brute_test01():' )
  print ( '  knapsack_brute() uses a brute force approach.' )
  print ( '  Maximize profit without exceeding weight limit.' )

  for test in range ( 6, 7 ):

    if ( test == 0 ):
      W = 26
      n = 5
      v = np.array ( [  24,  13,  23,  15,  16 ] )
      w = np.array ( [  12,   7,  11,   8,   9 ] )
    elif ( test == 1 ):
      W = 190
      n = 6
      v = np.array ( [  50,  50,  64,  46,  50,   5 ] )
      w = np.array ( [  56,  59,  80,  64,  75,  17 ] )
    elif ( test == 2 ):
      W = 50
      n = 7
      v = np.array ( [  70,  20,  39,  37,   7,   5,  10 ] )
      w = np.array ( [  31,  10,  20,  19,   4,   3,   6 ] )
    elif ( test == 3 ):
      W = 104
      n = 8
      v = np.array ( [ 350, 400, 450,  20,  70,   8,   5,   5 ] )
      w = np.array ( [  25,  35,  45,   5,  25,   3,   2,   2 ] )
    elif ( test == 4 ):
      W = 67
      n = 10
      v = np.array ( [ 505, 352, 458, 220, 354, 414, 498, 545, 473, 543 ] )
      w = np.array ( [  23,  26,  20,  18,  32,  27,  29,  26,  30,  27 ] )
    elif ( test == 5 ):
      W = 165
      n = 10
      v = np.array ( [  92,  57,  49,  68,  60,  43,  67,  84,  87,  72 ] )
      w = np.array ( [  23,  31,  29,  44,  53,  38,  63,  85,  89,  82 ] )
    elif ( test == 6 ):
      W = 170
      n = 7
      v = np.array ( [  442, 525, 511, 593, 546, 564, 617 ] )
      w = np.array ( [   41,  50,  49,  59,  55,  57,  60 ] )

    [ vmax, wmax, cmax ] = knapsack_brute ( n, v, w, W )

    print ( '' )
    print ( '  Problem ', test )
    print ( '  Weight limit is ', W )
    print ( '  Number of subsets is ', 2**n )
    print ( '   Item 0/1  Value  Weight  Value/Weight' )
    print ( '' )
    for i in range ( 0, n ):
      r = v[i] / w[i]
      print ( '  %5d  %2d  %5.0f  %5.0f  %7.2f' % ( i, cmax[i], v[i], w[i], r ) )
    print ( '' )
    print ( '  Taken  %2d  %5.0f  %5.0f  %7.2f' % \
    ( np.sum ( cmax ), np.sum ( vmax), np.sum ( wmax ), np.sum ( vmax ) / np.sum ( wmax ) ) )

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