#! /usr/bin/env python3
#
def knapsack_dynamic ( p, w, c ):

#*****************************************************************************80
#
## knapsack_dynamic() uses dynamic programming to solve a knapsack problem.
#
#  Discussion:
#
#    All data must be integers.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    02 November 2022
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#   integer p(n): the profit of each item.
#
#   integer w(n): the weight of each item.
#
#   integer c: the knapsack capacity.
#
#  Output:
#
#    integer item(): the list of item to be taken.
#
  import numpy as np

  m = knapsack_dynamic_table ( p, w, c )

  n = len ( p )
  item = np.array ( [], dtype = np.int )
  c2 = c

  for i in range ( n - 1, -1, -1 ):
    if ( m[i,c2] < m[i+1,c2] ):
      c2 = c2 - w[i]
      item = np.append ( item, i )

  return item

def knapsack_dynamic_table ( p, w, c ):

#*****************************************************************************80
#
## knapsack_dynamic_table() computes a knapsack problem dynamic programming table.
#
#  Discussion:
#
#    All data must be integers.
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    02 November 2022
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#   integer p(n): the profit of each item.
#
#   integer w(n): the weight of each item.
#
#   integer c: the knapsack capacity.
#
#  Output:
#
#    m(1:n+1,1:c+1): m(i+1,j+1) is the maximum value that can be stored in
#    the knapsack, selecting from the first i items, with a weight no more than j.
#
  import numpy as np

  n = len ( p )

  m = np.zeros ( [ n + 1, c + 1 ] )

  for i in range ( 0, n ):
    for j in range ( 0, c + 1 ):
      if ( j < w[i] ):
        m[i+1,j] = m[i,j]
      else:
        m[i+1,j] = max ( m[i,j], m[i,j-w[i]] + p[i] )

  return m

def knapsack_dynamic_test01 ( p, w, c ):

#*****************************************************************************80
#
## knapsack_dynamic_test01() tests knapsack_dynamic().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    02 November 2022
#
#  Author:
#
#    John Burkardt
#
#  Input:
#
#    integer p(n): the "profit" or value of each item.
#
#    integer w(n): the "weight" or cost of each item.
#
#    integer C: the maximum weight capacity for the knapsack.
#
  n = len ( p )

  print ( '' )
  print ( '  Number of items is', n )
  print ( '  Knapsack capacity is', c )
  print ( '  Item weights:' )
  print ( w )
  print ( '  Item values: ' )
  print ( p )

  item = knapsack_dynamic ( p, w, c )

  print ( '' )
  print ( '   #  Index  Weight  Value' )
  print ( '' )
  w_total = 0
  p_total = 0
  item_num = len ( item )
  for i in range ( 0, item_num ):
    j = item[i]
    print ( '  %2d     %2d   %5d  %5d' % ( i, item[i], w[j], p[j] ) )
    w_total = w_total + w[j]
    p_total = p_total + p[j]

  print ( '         --   -----  -----' )
  print ( '  Total: %2d   %5d  %5d' % ( item_num, w_total, p_total ) )

  return

def knapsack_dynamic_test ( ):

#*****************************************************************************80
#
## knapsack_dynamic_test() tests knapsack_dynamic().
#
#  Licensing:
#
#    This code is distributed under the MIT license.
#
#  Modified:
#
#    02 November 2022
#
#  Author:
#
#    John Burkardt
#
  import numpy as np
  import platform

  print ( '' )
  print ( 'knapsack_dynamic_test():' )
  print ( '  Python version: ' + platform.python_version ( ) )
  print ( '  Test knapsack_dynamic().' )

  for test in range ( 1, 7 ):

    if ( test == 1 ):
      c = 165
      n = 10
      p = 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 == 2 ):
      c = 26
      n = 5
      p = np.array ( [  24,  13,  23,  15,  16 ] )
      w = np.array ( [  12,   7,  11,   8,   9 ] )
    elif ( test == 3 ):
      c = 190
      n = 6
      p = np.array ( [  50,  50,  64,  46,  50,   5 ] )
      w = np.array ( [  56,  59,  80,  64,  75,  17 ] )
    elif ( test == 4 ):
      c = 50
      n = 7
      p = np.array ( [  70,  20,  39,  37,   7,   5,  10 ] )
      w = np.array ( [  31,  10,  20,  19,   4,   3,   6 ] )
    elif ( test == 5 ):
      c = 104
      n = 8
      p = np.array ( [ 350, 400, 450,  20,  70,   8,   5,   5 ] )
      w = np.array ( [  25,  35,  45,   5,  25,   3,   2,   2 ] )
    elif ( test == 6 ):
      c = 67
      n = 10
      p = 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 ] )

    knapsack_dynamic_test01 ( p, w, c )
#
#  Terminate.
#
  print ( '' )
  print ( 'knapsack_dynamic_test():' )
  print ( '  Normal end of execution.' )

  return

def timestamp ( ):

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

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

  return

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