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

# include "knapsack_01_brute.h"

int main ( );
void knapsack_01_brute_test01 ( );

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

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