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

# include "knapsack_01_brute.h"

int main ( );
void knapsack_01_brute_test01 ( );
void timestamp ( );

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

int main ( )

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

    knapsack_01_brute_test() tests knapsack_01_brute().

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    27 October 2022

  Author:

    John Burkardt
*/
{
  timestamp ( );
  printf ( "\n" );
  printf ( "knapsack_01_brute_test():\n" );
  printf ( "  C version.\n" );
  printf ( "  Test knapsack_01_brute().\n" );

  knapsack_01_brute_test01 ( );
/*
  Terminate.
*/
  printf ( "\n" );
  printf ( "knapsack_01_brute_test():\n" );
  printf ( "  Normal end of execution.\n" );
  printf ( "\n" );
  timestamp ( );

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

void knapsack_01_brute_test01 ( )

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

    knapsack_01_brute_test01() seeks a solution of the 0/1 Knapsack problem.

  Discussion:

    In the 0/1 knapsack problem, a knapsack of capacity C is given,
    as well as N items, with the I-th item of weight W(I).

    A selection is "acceptable" if the total weight is no greater than C.

    It is desired to find an optimal acceptable selection, that is,
    an acceptable selection such that there is no acceptable selection
    of greater weight.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    22 August 2014

  Author:

    John Burkardt
*/
{

  int c;
  int i;
  int n = 6;
  int *s;
  int t;
  int w[6] = {
    16, 17, 23, 24, 39, 40 };

  c = 100;

  printf ( "\n" );
  printf ( "knapsack_01_brute_test01():\n" );
  printf ( "  Knapsack maximum capacity is %d\n", c );
  printf ( "  Come as close as possible to filling the knapsack.\n" );

  s = knapsack_01_brute ( n, w, c );

  printf ( "\n" );
  printf ( "   # 0/1  Weight\n" );
  printf ( "\n" );
  for ( i = 0; i < n; i++ )
  {
    printf ( "  %2d  %1d  %4d\n", i, s[i], w[i] );
  }
  t = 0;
  for ( i = 0; i < n; i++ )
  {
    t = t + s[i] * w[i];
  }
  printf ( "\n" );
  printf ( "  Total:   %d\n", t );

  free ( s );

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

void timestamp ( )

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

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

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

  return;
# undef TIME_SIZE
}