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

# include "knapsack_brute.h"

int main ( );
void knapsack_brute_test01 ( );
void knapsack_values ( int *n_data, int *n, int *v, int *w, int *s, int *k );
void subset_next_test ( );
void timestamp ( );

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

int main ( )

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

    knapsack_brute_test() tests knapsack_brute().
!
!  Licensing:
!
!    This code is distributed under the MIT license.
!
!  Modified:
!
!    26 November 2015
!
!  Author:
!
!    John Burkardt
*/
{
  timestamp ( );

  printf ( "\n" );
  printf ( "knapsack_brute_test():\n" );
  printf ( "  C version\n" );
  printf ( "  Test knapsack_brute()\n" );

  subset_next_test ( );
  knapsack_brute_test01 ( );
/*
  Terminate.
*/
  printf ( "\n" );
  printf ( "knapsack_brute_test():\n" );
  printf ( "  Normal end of execution.\n" );

  timestamp ( );

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

void knapsack_brute_test01 ( )

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

    knapsack_brute_test01() tests knapsack_brute().

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    27 November 2024

  Author:

    John Burkardt
*/
{
  float *d;
  int i;
  int k;
  int n;
  int n_data;
  int *s;
  int *smax;
  int *v;
  int vmax;
  int *w;
  int wmax;

  printf ( "\n" );
  printf ( "knapsack_brute_test01():\n" );
  printf ( "  knapsack_brute() uses a brute force approach.\n" );
  printf ( "  Maximize profit without exceeding weight limit.\n" );

  n_data = 0;

  while ( true )
  {
/*
   First call returns value of n.
*/
    n = 0;
    knapsack_values ( &n_data, &n, v, w, s, &k );

    if ( n == 0 )
    {
      break;
    }

    d = ( float * ) malloc ( n * sizeof ( float ) );
    v = ( int * ) malloc ( n * sizeof ( int ) );
    w = ( int * ) malloc ( n * sizeof ( int ) );
    s = ( int * ) malloc ( n * sizeof ( int ) );
    smax = ( int * ) malloc ( n * sizeof ( int ) );
/*
  Second call returns data, and increments n_data.
*/
    knapsack_values ( &n_data, &n, v, w, s, &k );

    for ( i = 0; i < n; i++ )
    {
      d[i] = ( float ) ( v[i] ) / ( float ) ( w[i] );
    }

    knapsack_brute ( n, v, w, k, &vmax, &wmax, smax );

    printf ( "\n" );
    printf ( "  Problem %d\n", n_data );
    printf ( "  Number of items is %d\n", n );
    printf ( "  Knapsack weight limit is %d\n", k );
    printf ( "\n" );
    printf ( "   Item 0/1  Value  Weight  Density\n" );
    printf ( "\n" );
    for ( i = 0; i < n; i++ )
    {
      printf ( "  %5d  %2d  %8d  %8d  %7.2f\n", i, smax[i], v[i], w[i], d[i] );
    }
    printf ( "\n" );
    printf ( "  Taken  %2d  %8d  %8d  %7.2f\n",
      i4vec_sum ( n, smax ), 
      i4vec_dot_product ( n, smax, v ), 
      i4vec_dot_product ( n, smax, w ), 
      ( float ) ( i4vec_dot_product ( n, smax, v ) ) / 
      ( float ) ( i4vec_dot_product ( n, smax, w ) ) );

    free ( d );
    free ( s );
    free ( smax );
    free ( v );
    free ( w );
  }

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

void knapsack_values ( int *n_data, int *n, int *v, int *w, int *s, int *k )

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

    knapsack_values() returns samples of the knapsack problem.

  Discussion:

    Convincing C to allow an array of varying dimension to be created, 
    initialized in a single statement, and passed back as a function argument
    shows me that sometimes C is a real caveman language.  

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    19 November 2024

  Author:

    John Burkardt

  Input on first call:

    int *n_data: the user sets n_data to 0 before the first call.  

  Output on first call:

    int *n: the size of the arrays for this problem.
    But if n is returned as 0, then there are no more data examples.

  Input on second call:

    int *n_data: the same value as on the previous call.  

    int *n: the number of items

  Output on second call:

    int *n_data: on each call, the routine increments n_data by 1, and
    returns the corresponding data when there is no more data, the
    output value of n_data will be 0 again.

    int v(n): the value of each item

    int w(n): the weight of each item

    int s(n): 1 if the item is used in the optimal solution, 0 otherwise.

    int *k: the weight capacity of the knapsack.
*/
{
  const int n_max = 10;

  if ( *n_data == n_max )
  {
    *n_data = 0;
    *n = 0;
    *k = 0;
    return;
  }
/*
  If n == 0, this is the first call for this problem.
  Return n, so user can allocate array sizes.
*/
  if ( *n == 0 )
  {
    if ( *n_data == 0 )
    {
      *n = 5;
    }
    else if ( *n_data == 1 )
    {
      *n = 6;
    }
    else if ( *n_data == 2 )
    {
      *n = 6;
    }
    else if ( *n_data == 3 )
    {
      *n = 7;
    }
    else if ( *n_data == 4 )
    {
      *n = 7;
    }
    else if ( *n_data == 5 )
    {
      *n = 8;
    }
    else if ( *n_data == 6 )
    {
      *n = 10;
    }
    else if ( *n_data == 7 )
    {
      *n = 10;
    }
    else if ( *n_data == 8 )
    {
      *n = 15;
    }
    else if ( *n_data == 9 )
    {
      *n = 24;
    }
    return;
  }

  if ( *n_data == 0 )
  {
    *n = 5;
    memcpy ( v, ( int[] ) {  24,  13,  23,  15,  16 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  12,   7,  11,   8,   9 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   0,   1,   1,   1,   0 }, *n * sizeof ( int ) );
    *k = 26;
  }
  else if ( *n_data == 1 )
  {
    *n = 6;
    memcpy ( v, ( int[] ) {  50,  50,  64,  46,  50,   5 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  56,  59,  80,  64,  75,  17 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   1,   1,   0,   0,   1,   0 }, *n * sizeof ( int ) );
    *k = 190;
  }
  else if ( *n_data == 2 )
  {
    *n = 6;
    memcpy ( v, ( int[] ) {  175, 90, 20, 50, 10, 200 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  10,   9,  4,  2,  1,  20 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   1,   1,  0,  0,  1,   0 }, *n * sizeof ( int ) );
    *k = 20;
  }
  else if ( *n_data == 3 )
  {
    *n = 7;
    memcpy ( v, ( int[] ) {  70,  20,  39,  37,   7,   5,  10 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  31,  10,  20,  19,   4,   3,   6 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   1,   0,   0,   1,   0,   0,   0 }, *n * sizeof ( int ) );
    *k = 50;
  }
  else if ( *n_data == 4 )
  {
    *n = 7;
    memcpy ( v, ( int[] ) { 442, 525, 511, 593, 546, 564, 617 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  41,  50,  49,  59,  55,  57,  60 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   1,   0,   0,   1,   0,   0,   1 }, *n * sizeof ( int ) );
    *k = 170;
  }
  else if ( *n_data == 5 )
  {
    *n = 8;
    memcpy ( v, ( int[] ) { 350, 400, 450,  20,  70,   8,   5,   5 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  25,  35,  45,   5,  25,   3,   2,   2 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   1,   0,   1,   1,   1,   0,   1,   1 }, *n * sizeof ( int ) );
    *k = 104;
  }
  else if ( *n_data == 6 )
  {
    *n = 10;
    memcpy ( v, ( int[] ) { 505, 352, 458, 220, 354, 414, 498, 545, 473, 543 },
      *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  23,  26,  20,  18,  32,  27,  29,  26,  30,  27 },
      *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   1,   0,   0,   1,   0,   0,   0,   1,   0,   0 },
      *n * sizeof ( int ) );
    *k = 67;
  }
  else if ( *n_data == 7 )
  {
    *n = 10;
    memcpy ( v, ( int[] ) {  92,  57,  49,  68,  60,  43,  67,  84,  87,  72 },
      *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  23,  31,  29,  44,  53,  38,  63,  85,  89,  82 },
      *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {   1,   1,   1,   1,   0,   1,   0,   0,   0,   0 },
      *n * sizeof ( int ) );
    *k = 165;
  }
  else if ( *n_data == 8 )
  {
    *n = 15;
    memcpy ( v, ( int[] ) {  135, 139, 149, 150, 156, 163, 173, 184, 192, 201, 
                 210, 214, 221, 229, 240 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {   70,  73,  77,  80,  82,  87,  90,  94,  98, 106, 
                 110, 113, 115, 118, 120 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {    1,   0,   1,   0,   1,   0,   1,   1,   1,   0, 
                   0,   0,   0,   1,   1 }, *n * sizeof ( int ) );
    *k = 750;
  }
  else if ( *n_data == 9 )
  {
    *n = 24;
    memcpy ( v, ( int[] ) {  825594, 1677009, 1676628, 1523970,  943972, 
                  97426,   69666, 1296457, 1679693, 1902996, 
                1844992, 1049289, 1252836, 1319836,  953277, 
                2067538,  675367,  853655, 1826027,   65731, 
                 901489,  577243,  466257,  369261 }, *n * sizeof ( int ) );
    memcpy ( w, ( int[] ) {  382745,  799601,  909247,  729069,  467902, 
                  44328,   34610,  698150,  823460,  903959, 
                 853665,  551830,  610856,  670702,  488960, 
                 951111,  323046,  446298,  931161,   31385, 
                 496951,  264724,  224916,  169684 }, *n * sizeof ( int ) );
    memcpy ( s, ( int[] ) {       1,       1,       0,       1,       1, 
                      1,       0,       0,       0,       1, 
                      1,       0,       1,       0,       0, 
                      1,       0,       0,       0,       0, 
                      0,       1,       1,       1 }, *n * sizeof ( int ) );
    *k = 6404180;
  }
  *n_data = *n_data + 1;

  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 = 5;
  int *s;

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

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

  s = ( int * ) malloc ( n * sizeof ( int ) );
  for ( i = 0; i < n; i++ )
  {
    s[i] = 0;
  }
  i = -1;

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

    subset_next ( n, s );

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

  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
}