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

#*****************************************************************************80
#
## knapsack_rational_test() tests knapsack_rational().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    16 November 2024
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'knapsack_rational_test():' )
  print ( '  python version: ' + platform.python_version ( ) )
  print ( '  numpy version:  ' + np.version.version )
  print ( '  Test knapsack_rational().' )

  knapsack_rational_tester ( )
  knapsack_reorder_test ( )
#
#  Terminate.
#
  print ( '' )
  print ( 'knapsack_rational_test():' )
  print ( '  Normal end of execution.' )
  return

def knapsack_rational ( n, mass_limit, p, w ):

#*****************************************************************************80
#
## knapsack_rational() solves the rational knapsack problem.
#
#  Discussion:
#
#    The rational knapsack problem is a generalization of the 0/1 knapsack
#    problem.  It is mainly used to derive a bounding function for the
#    0/1 knapsack problem.
#
#    The 0/1 knapsack problem is as follows:
#
#      Given:
#        a set of N objects,
#        a profit P(I) and weight W(I) associated with each object,
#        and a weight limit MASS_LIMIT,
#      Determine:
#        a set of choices X(I) which are 0 or 1, that maximizes the profit
#          P = Sum ( 1 <= I <= N ) P(I) * X(I)
#        subject to the constraint
#          Sum ( 1 <= I <= N ) W(I) * X(I) <= MASS_LIMIT.
#
#    By contrast, the rational knapsack problem allows the values X(I)
#    to be any value between 0 and 1.  A solution for the rational knapsack
#    problem is known.  Arrange the objects in order of their "profit density"
#    ratios P(I)/W(I), and then take in order as many of these as you can.
#    If you still have "room" in the weight constraint, then you should
#    take the maximal fraction of the very next object, which will complete
#    your weight limit, and maximize your profit.
#
#    If should be obvious that, given the same data, a solution for
#    the rational knapsack problem will always have a profit that is
#    at least as high as for the 0/1 problem.  Since the rational knapsack
#    maximum profit is easily computed, this makes it a useful bounding
#    function.
#
#    Note that this routine assumes that the objects have already been
#    arranged in order of the "profit density".
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 December 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Donald Kreher, Douglas Simpson,
#    Combinatorial Algorithms,
#    CRC Press, 1998,
#    ISBN: 0-8493-3988-X,
#    LC: QA164.K73.
#
#  Input:
#
#    integer N, the number of objects.
#
#    real MASS_LIMIT, the weight limit of the
#    chosen objects.
#
#    real P(N), the "profit" or value of each object.
#    The entries of P are assumed to be nonnegative.
#
#    real W(N), the "weight" or cost of each object.
#    The entries of W are assumed to be nonnegative.
#
#  Output:
#
#    real X(N), the choice function for the objects.
#    0.0, the object was not taken.
#    1.0, the object was taken.
#    R, where 0 < R < 1, a fractional amount of the object was taken.
#
#    real MASS, the total mass of the objects taken.
#
#    real PROFIT, the total profit of the objects taken.
#
  import numpy as np

  x = np.zeros ( n )
  mass = 0.0
  profit = 0.0

  for i in range ( 0, n ):

    if ( mass_limit <= mass ):
      x[i] = 0.0
    elif ( mass + w[i] <= mass_limit ):
      x[i] = 1.0
      mass = mass + w[i]
      profit = profit + p[i]
    else:
      x[i] = ( mass_limit - mass ) / w[i]
      mass = mass_limit
      profit = profit + p[i] * x[i]

  return x, mass, profit

def knapsack_rational_tester ( ):

#*****************************************************************************80
#
## knapsack_rational_tester() tests knapsack_rational().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    25 January 2011
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  n = 5

  mass_limit = 26.0
  p = np.array ( [ 24.0, 13.0, 23.0, 15.0, 16.0 ] )
  w = np.array ( [ 12.0,  7.0, 11.0,  8.0,  9.0 ] )

  print ( '' )
  print ( 'knapsack_rational_tester():' )
  print ( '  knapsack_rational() solves the rational knapsack problem.' )

  print ( '' )
  print ( '  Object, Profit, Mass, "Profit Density"' )
  print ( '' )
  for i in range ( 0, n ):
    print ( '  %6d  %7.3f  %7.3f  %7.3f' % ( i, p[i], w[i], p[i] / w[i] ) )

  p, w = knapsack_reorder ( n, p, w )

  print ( '' )
  print ( '  After reordering by Profit Density:' )
  print ( '' )
  print ( '  Object, Profit, Mass, "Profit Density"' )
  print ( '' )
  for i in range ( 0, n ):
    print ( '  %6d  %7.3f  %7.3f  %7.3f' % ( i, p[i], w[i], p[i] / w[i] ) )

  print ( '' )
  print ( '  Total mass restriction is %f' % ( mass_limit ) )

  x, mass, profit = knapsack_rational ( n, mass_limit, p, w  )

  print ( '' )
  print ( '  Object, Density, Choice, Profit, Mass' )
  print ( '' )
  for i in range ( 0, n ):
    print ( '%6d  %7.3f  %7.3f  %7.3f  %7.3f' \
      % ( i, p[i] / w[i], x[i], x[i] * p[i], x[i] * w[i] ) )

  print ( '' )
  print ( '  Total:                  %7.3f  %7.3f' % ( profit, mass ) )

  return

def knapsack_reorder ( n, p, w ):

#*****************************************************************************80
#
## knapsack_reorder() reorders the knapsack data by "profit density".
#
#  Discussion:
#
#    This routine must be called to rearrange the data before calling
#    routines that handle a knapsack problem.
#
#    The "profit density" for object I is defined as P(I)/W(I).
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 December 2015
#
#  Author:
#
#    John Burkardt
#
#  Reference:
#
#    Donald Kreher, Douglas Simpson,
#    Combinatorial Algorithms,
#    CRC Press, 1998,
#    ISBN: 0-8493-3988-X,
#    LC: QA164.K73.
#
#  Input:
#
#    integer N, the number of objects.
#
#    real P(N), the "profit" or value of each object.
#
#    real W(N), the "weight" or cost of each object.
#
#  Output:
#
#    real P(N), the reordered "profit" or value of each object.
#
#    real W(N), the reordered "weight" or cost of each object.
#

#
#  Rearrange the objects in order of "profit density".
#
  for i in range ( 0, n ):
    for j in range ( i + 1, n ):

      if ( p[i] * w[j] < p[j] * w[i] ):

        t    = p[i]
        p[i] = p[j]
        p[j] = t

        t    = w[i]
        w[i] = w[j]
        w[j] = t

  return p, w

def knapsack_reorder_test ( ):

#*****************************************************************************80
#
## knapsack_reorder_test() tests knapsack_reorder().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    24 December 2015
#
#  Author:
#
#    John Burkardt
#
  import numpy as np

  n = 5
  p = np.array ( [ 24.0, 13.0, 23.0, 15.0, 16.0 ] )
  w = np.array ( [ 12.0,  7.0, 11.0,  8.0,  9.0 ] )

  print ( '' )
  print ( 'knapsack_reorder_test():' )
  print ( '  knapsack_reorder() reorders knapsack data.' )

  print ( '' )
  print ( '  Object, Profit, Mass, "Profit Density"' )
  print ( '' )
  for i in range ( 0, n ):
    print ( '  %6d  %7.3f  %7.3f  %7.3f' % ( i, p[i], w[i], p[i] / w[i] ) )

  p, w = knapsack_reorder ( n, p, w )

  print ( '' )
  print ( '  After reordering by Profit Density:' )
  print ( '' )
  print ( '  Object, Profit, Mass, "Profit Density"' )
  print ( '' )
  for i in range ( 0, n ):
    print ( '  %6d  %7.3f  %7.3f  %7.3f' % ( i, p[i], w[i], p[i] / w[i] ) )

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