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

using namespace std;

# include "knapsack_values.hpp"

int main ( );
int i4vec_dot_product ( int n, int x[], int y[] );
int i4vec_sum ( int n, int a[] );
void timestamp ( );

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

int main ( )

//****************************************************************************80
//
//  Purpose:
//
//    knapsack_values_test() tests knapsack_values().
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    20 November 2024
//
//  Author:
//
//    John Burkardt
//
{
  int i;
  int k;
  int n;
  int n_data;
  double r;
  int *s;
  int *v;
  int *w;

  timestamp ( );

  cout << "\n";
  cout << "knapsack_values_test():\n";
  cout << "  C++ version,\n";
  cout << "  Test knapsack_values().\n";

  n_data = 0;

  while ( true )
  {
//
//  First call to get the problem size N.
//
    n = 0;
    knapsack_values ( &n_data, &n, v, w, s, &k );

    if ( n == 0 )
    {
      break;
    }
//
//  Allocate array space, and call again for array data.
//
    s = ( int * ) malloc ( n * sizeof ( int ) );
    v = ( int * ) malloc ( n * sizeof ( int ) );
    w = ( int * ) malloc ( n * sizeof ( int ) );

    knapsack_values ( &n_data, &n, v, w, s, &k );

    cout << "\n";
    cout << "  Problem #" << n_data << "\n";
    cout << "  Number of items is " << n << "\n";
    cout << "  Knapsack weight limit is " << k << "\n";
    cout << "\n";
    cout << "   Item 0/1  Value  Weight  Value/Weight\n";
    cout << "\n";
    for( i = 0; i < n; i++ )
    {
      r = ( double ) v[i] / ( double ) w[i];
      cout << "  " << setw(5) << i
           << "  " << setw(2) << s[i]
           << "  " << setw(8) << v[i]
           << "  " << setw(8) << w[i]
           << "  " << setw(8) << setprecision(3) << r << "\n";
    }
    cout << "\n";
    cout << "  Taken"
      << "  " << setw(2) << i4vec_sum ( n, s )
      << "  " << setw(8) << i4vec_dot_product ( n, s, v )
      << "  " << setw(8) << i4vec_dot_product ( n, s, w )
      << "  " << setw(8) << setprecision(3) << 
        ( double ) i4vec_dot_product ( n, s, v ) / 
        ( double ) i4vec_dot_product ( n, s, w ) << "\n";

    free ( s );
    free ( w );
    free ( v );
  }
//
//  Terminate.
//
  cout << "\n";
  cout << "knapsack_values_test():\n";
  cout << "  Normal end of execution.\n";
  cout << "\n";

  timestamp ( );

  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

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

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

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

  now = time ( NULL );
  tm = localtime ( &now );

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

  cout << time_buffer << "\n";

  return;
# undef TIME_SIZE
}