# include <cstdlib>
# include <cstring>
# include <ctime>
# include <iomanip>
# include <iostream>

using namespace std;

# include "knapsack_random.hpp"

int main ( );
int i4vec_dot_product ( int n, int x[], int y[] );
void i4vec_print ( int n, int a[], string title );
int i4vec_sum ( int n, int a[] );
void knapsack_random_test01 ( );
void subset_next_test ( );
void subset_random_test ( );
void timestamp ( );

//****************************************************************************80

int main ( )

//****************************************************************************80
//
//  Purpose:
//
//    knapsack_random_test() tests knapsack_random().
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    30 November 2024
//
//  Author:
//
//    John Burkardt
//
{
  timestamp ( );

  cout << "\n";
  cout << "knapsack_random_test():\n";
  cout << "  C++ version\n";
  cout << "  Test knapsack_random()\n";

  subset_next_test ( );
  subset_random_test ( );
  knapsack_random_test01 ( );
//
//  Terminate.
//
  cout << "\n";
  cout << "knapsack_random_test():\n";
  cout << "  Normal end of execution.\n";

  return 0;
}
//****************************************************************************80

int i4vec_dot_product ( int n, int x[], int y[] )

//****************************************************************************80
//
//  Purpose:
//
//    i4vec_dot_product() computes the dot product of two I4VEC's.
//
//  Discussion:
//
//    An I4VEC is a vector of I4's.
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    19 December 2011
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int N, the size of the array.
//
//    int X[N], Y[N], the arrays.
//
//  Output:
//
//    int I4VEC_DOT_PRODUCT, the dot product of X and Y.
//
{
  int i;
  int value;

  value = 0;
  for ( i = 0; i < n; i++ )
  {
    value = value + x[i] * y[i];
  }

  return value;
}
//****************************************************************************80

void i4vec_print ( int n, int a[], string title )

//****************************************************************************80
//
//  Purpose:
//
//    i4vec_print() prints an I4VEC.
//
//  Discussion:
//
//    An I4VEC is a vector of I4's.
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    14 November 2003
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int N, the number of components of the vector.
//
//    int A[N], the vector to be printed.
//
//    string TITLE, a title.
//
{
  int i;

  cout << "\n";
  cout << title << "\n";
  cout << "\n";
  for ( i = 0; i < n; i++ )
  {
    cout << "  " << setw(8) << i
         << ": " << setw(8) << a[i]  << "\n";
  }
  return;
}
//****************************************************************************80

int i4vec_sum ( int n, int a[] )

//****************************************************************************80
//
//  Purpose:
//
//    i4vec_sum() sums the entries of an I4VEC.
//
//  Discussion:
//
//    An I4VEC is a vector of I4's.
//
//  Example:
//
//    Input:
//
//      A = ( 1, 2, 3, 4 )
//
//    Output:
//
//      I4VEC_SUM = 10
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    26 May 1999
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    int N, the number of entries in the vector.
//
//    int A[N], the vector to be summed.
//
//  Output:
//
//    int I4VEC_SUM, the sum of the entries of A.
//
{
  int i;
  int sum;

  sum = 0;
  for ( i = 0; i < n; i++ )
  {
    sum = sum + a[i];
  }

  return sum;
}
//****************************************************************************80

void knapsack_random_test01 ( )

//****************************************************************************80
//
//  Purpose:
//
//    knapsack_random_test01() tests knapsack_random().
//
//  Discussion:
//
//    In the knapsack problem, a knapsack of capacity K is given,
//    as well as N items, with the I-th item of value V(I) and weight W(I).
//
//    A selection is "feasible" if the total weight is no greater than K.
//
//    A selection is "optimal" if it is feasible, and the total value of
//    the selected items is not exceeded for any other feasible selection
//
//    This code simply chooses a selection at random, determines if it is
//    feasible, and if so, reports the total value of the selection.
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    30 November 2024
//
//  Author:
//
//    John Burkardt
//
{
  int c_test[5];
  int k = 26;
  int n = 5;
  float r_test;
  int test;
  int v[5] = { 24,  13, 23,  15,  16 };
  int v_test;
  int w[5] = { 12,  7,  11,   8,   9 };
  int w_test;

  cout << "\n";
  cout << "knapsack_random_test01():\n";
  cout << "  knapsack_random() randomly selects a subset of n items\n";
  cout << "  and considers it as a solution to a knapsack problem.\n";
  cout << "  Maximize profit without exceeding weight limit.\n";

  cout << "\n";
  cout << "  Number of items is " << n << "\n";
  i4vec_print ( n, v, "  Value array:" );
  i4vec_print ( n, w, "  Weight array:" );
  cout << "  Weight limit is " << k << "\n";

  for ( test = 1; test <= 10; test++ )
  {
    knapsack_random ( n, c_test );
    v_test = i4vec_dot_product ( n, c_test, v );
    w_test = i4vec_dot_product ( n, c_test, w );
    if ( 0.0 < w_test )
    {
      r_test = ( float ) ( v_test ) / ( float ) ( w_test );
    }
    else
    {
      r_test = 0.0;
    }

    cout << "\n";
    i4vec_print ( n, c_test, "  Selected items:" );
    if ( k < w_test )
    {
      cout << "  Weight " << w_test << " exceeds weight limit " << k << "\n";
    }
    else
    {
      cout << "  Weight " << w_test << "\n";
      cout << "  Value  " << v_test << "\n";
      cout << "  Ratio  " << r_test << "\n";
    }

  }

  return;
}
//****************************************************************************80

void subset_next_test ( )

//****************************************************************************80
//
//  Purpose:
//
//    subset_next_test() tests subset_next().
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    30 November 2024
//
//  Author:
//
//    John Burkardt
//
{
  int i;
  int j;
  int n;
  int *s;

  cout << "\n";
  cout << "subset_next_test():\n";
  cout << "  Test subset_next()\n";
  cout << "\n";

  n = 5;
  s = new int[n];

  cout << "  Generate in order subsets of size " << n << "\n";
  cout << "\n";

  for ( j = 0; j < n; j++ )
  {
    s[j] = 0;
  }

  i = -1;
  while ( true )
  {
    i = i + 1;
    cout << "  " << setw(2) << i << ":";
    for ( j = 0; j < n; j++ )
    {
      cout << "  " << s[j];
    }
    cout << "\n";
    subset_next ( n, s );

    if ( i4vec_sum ( n, s ) == 0 )
    {
      break;
    }
  }

  delete [] s;

  return;
}
//****************************************************************************80

void subset_random_test ( )

//****************************************************************************80
//
//  Purpose:
//
//    subset_random_test() tests subset_random().
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    30 November 2024
//
//  Author:
//
//    John Burkardt
//
{
  int i;
  int index;
  int n = 5;
  int *s;
  int test;

  cout << "\n";
  cout << "subset_random_test():\n";
  cout << "  Test subset_random()\n";
  cout << "\n";

  cout << "  Subsets will be of size n = " << n << "\n";
  cout << "\n";

  s = new int[n];

  for ( test = 1; test <= 10; test++ )
  {
    subset_random ( n, s );
    index = subset_to_rank ( n, s );
    cout << "  " << setw(2) << index << ":";
    for ( i = 0; i < n; i++ )
    {
      cout << "  " << s[i];
    }
    cout << "\n";
  }

  delete [] s;

  return;
}
//****************************************************************************80

void timestamp ( )

//****************************************************************************80
//
//  Purpose:
//
//    timestamp() prints the current YMDHMS date as a time stamp.
//
//  Example:
//
//    31 May 2001 09:45:54 AM
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    19 March 2018
//
//  Author:
//
//    John Burkardt
//
{
# define TIME_SIZE 40

  static char time_buffer[TIME_SIZE];
  const struct std::tm *tm_ptr;
  std::time_t now;

  now = std::time ( NULL );
  tm_ptr = std::localtime ( &now );

  std::strftime ( time_buffer, TIME_SIZE, "%d %B %Y %I:%M:%S %p", tm_ptr );

  std::cout << time_buffer << "\n";

  return;
# undef TIME_SIZE
}