#! /usr/bin/env python3
#
def knapsack_01_brute ( n, w, c ):

#*****************************************************************************80
#
## KNAPSACK_01_BRUTE seeks a solution of the 0/1 Knapsack problem.
#
#  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 GNU LGPL license.
#
#  Modified:
#
#    13 November 2015
#
#  Author:
#
#    John Burkardt
#
#  Parameters:
#
#    Input, integer N, the number of weights.
#
#    Input, integer W(N), the weights.
#
#    Input, integer C, the maximum weight.
#
#    Output, integer S[N], is a binary vector which defines an optimal
#    selection.  It is 1 for the weights to be selected, and 0 otherwise.
#
  import numpy as np
  from subset_gray_next import subset_gray_next

  more = False
  ncard = 0

  s_test = np.zeros ( n )
  t_test = 0

  s_opt = np.zeros ( n )
  t_opt = 0;

  while ( True ):

    s_test, more, ncard, iadd = subset_gray_next ( n, s_test, more, ncard )
    t_test = 0
    for i in range ( 0, n ):
      t_test = t_test + s_test[i] * w[i]

    if ( t_opt < t_test and t_test <= c ):
      t_opt = t_test
      for i in range ( 0, n ):
        s_opt[i] = s_test[i]

    if ( not more ):
      break

  return s_opt

def knapsack_01_brute_test ( ):

#*****************************************************************************80
#
## KNAPSACK_01_BRUTE+TEST seeks a solution of the 0/1 Knapsack problem.
#
#  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 GNU LGPL license.
#
#  Modified:
#
#    13 November 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  w = np.array ( [ 16, 17, 23, 24, 39, 40 ] )
  c = 100
  n = 6

  print ( '' )
  print ( 'KNAPSACK_01_BRUTE_TEST:' )
  print ( '  Python version: %s' % ( platform.python_version ( ) ) )
  print ( '  Knapsack maximum capacity is %d' % ( c ) )
  print ( '  Come as close as possible to filling the knapsack.' )

  s = knapsack_01_brute ( n, w, c )

  print ( '' )
  print ( '   # 0/1  Weight' )
  print ( '' )
  total = 0
  for i in range ( 0, n ):
    total = total + s[i] * w[i]
    print ( '  %2d  %1d  %4d' % ( i, s[i], w[i] ) )
  print ( '' )
  print ( '  Total: %4d' % ( total ) )
#
#  Terminate.
#
  print ( '' )
  print ( 'KNAPSACK_01_BRUTE_TEST' )
  print ( '  Normal end of execution.' )
  return

if ( __name__ == '__main__' ):
  from timestamp import timestamp
  timestamp ( )
  knapsack_01_brute_test ( )
  timestamp ( )