# include <stdbool.h>
# include <stdio.h>
# include <stdlib.h>
# include <time.h>

# include "knapsack_random.h"

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

/******************************************************************************/

int main ( )

/******************************************************************************/
/*
  Purpose:

    knapsack_random_test() tests knapsack_random().

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    29 November 2015

  Author:

    John Burkardt
*/
{
  timestamp ( );

  printf ( "\n" );
  printf ( "knapsack_random_test():\n" );
  printf ( "  C version\n" );
  printf ( "  Test knapsack_random()\n" );

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

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

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

/******************************************************************************/
/*
  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;
}
/******************************************************************************/

void i4vec_print ( int n, int a[], char *title )

/******************************************************************************/
/*
  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.

    char *TITLE, a title.
*/
{
  int i;

  fprintf ( stdout, "\n" );
  fprintf ( stdout, "%s\n", title );
  fprintf ( stdout, "\n" );

  for ( i = 0; i < n; i++ )
  {
    fprintf ( stdout, "  %6d: %8d\n", i, a[i] );
  }
  return;
}
/******************************************************************************/

int i4vec_sum ( int n, int a[] )

/******************************************************************************/
/*
  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:

    29 May 2003

  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;
}
/******************************************************************************/

void knapsack_random_test01 ( )

/******************************************************************************/
/*
  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:

    29 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;

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

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

  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;
    }

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

  }

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

void subset_next_test ( )

/******************************************************************************/
/*
  Purpose:

    subset_next_test() tests subset_next().

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    25 November 2024

  Author:

    John Burkardt
*/
{
  int i;
  int j;
  int n;
  int *s;

  printf ( "\n" );
  printf ( "subset_next_test():\n" );
  printf ( "  Test subset_next()\n" );
  printf ( "\n" );

  n = 5;
  s = ( int * ) malloc ( n * sizeof ( int ) );

  printf ( "  Generate in order subsets of size %d\n", n );
  printf ( "\n" );

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

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

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

  free ( s );

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

void subset_random_test ( )

/******************************************************************************/
/*
  Purpose:

    subset_random_test() tests subset_random().

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    29 November 2024

  Author:

    John Burkardt
*/
{
  int i;
  int index;
  int n = 5;
  int *s;
  int test;

  printf ( "\n" );
  printf ( "subset_random_test():\n" );
  printf ( "  Test subset_random()\n" );
  printf ( "\n" );

  printf ( "  Subsets will be of size n = %d\n", n );
  printf ( "\n" );

  s = ( int * ) malloc ( n * sizeof ( int ) );

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

  free ( s );

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

void timestamp ( )

/******************************************************************************/
/*
  Purpose:
 
    timestamp() prints the current YMDHMS date as a time stamp.

  Example:

    17 June 2014 09:45:54 AM

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    01 May 2021

  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 );

  printf ( "%s\n", time_buffer );

  return;
# undef TIME_SIZE
}