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

using namespace std;

# include "knapsack_brute.hpp"

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

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

int main ( )

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

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

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

  timestamp ( );

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

void knapsack_brute_test01 ( )

//****************************************************************************80
//
//  Purpose:
//
//    knapsack_brute_test01() tests knapsack_brute().
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    28 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;

  cout << "\n";
  cout << "knapsack_brute_test01():\n";
  cout << "  knapsack_brute() uses a brute force approach.\n";
  cout << "  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 = new float[n];
    v = new int[n];
    w = new int[n];
    s = new int[n];
    smax = new int[n];
//
//  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 );

    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  Density\n";
    cout << "\n";
    for ( i = 0; i < n; i++ )
    {
      cout << "  " << setw(5) << i
           << "  " << setw(2) << smax[i]
           << "  " << setw(8) << v[i]
           << "  " << setw(8) << w[i]
           << "  " << setw(7) << d[i] << "\n";
    }
    cout << "\n";
    cout << "  Taken"
         << "  " << setw(2) << i4vec_sum ( n, smax )
         << "  " << setw(8) << i4vec_dot_product ( n, smax, v )
         << "  " << setw(8) << i4vec_dot_product ( n, smax, w )
         << "  " << setw(7) << ( float ) ( i4vec_dot_product ( n, smax, v ) ) / 
                               ( float ) ( i4vec_dot_product ( n, smax, w ) );

    delete [] d;
    delete [] s;
    delete [] smax;
    delete [] v;
    delete [] w;
  }

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

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

//****************************************************************************80
//
//  Purpose:
//
//    knapsack_values() returns samples of the knapsack problem.
//
//  Discussion:
//
//    Even more so than C, C++ is unable to deal with defining and
//    initializing an array in a function to be returned as an argument.  
//    So now I have to initialize my arrays like a donkey would.
//
//  Licensing:
//
//    This code is distributed under the MIT license. 
//
//  Modified:
//
//    20 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.
//
{
  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;
    v[0] = 24;
    v[1] = 13;
    v[2] = 23;
    v[3] = 15;
    v[4] = 16;
    w[0] = 12;
    w[1] =  7;
    w[2] = 11;
    w[3] =  8;
    w[4] =  9;
    s[0] =  0;
    s[1] =  1;
    s[2] =  1;
    s[3] =  1;
    s[4] =  0;
    *k = 26;
  }
  else if ( *n_data == 1 )
  {
    *n = 6;
    v[0] = 50;
    v[1] = 50;
    v[2] = 64;
    v[3] = 46;
    v[4] = 50;
    v[5] =  5;
    w[0] = 56;
    w[1] = 59;
    w[2] = 80;
    w[3] = 64;
    w[4] = 75;
    w[5] = 17;
    s[0] =  1;
    s[1] =  1;
    s[2] =  0;
    s[3] =  0;
    s[4] =  1;
    s[5] =  0;
    *k = 190;
  }
  else if ( *n_data == 2 )
  {
    *n = 6;
    v[0] = 175;
    v[1] =  90;
    v[2] =  20;
    v[3] =  50;
    v[4] =  10;
    v[5] = 200;
    w[0] =  10;
    w[1] =   9;
    w[2] =   4;
    w[3] =   2;
    w[4] =   1;
    w[5] =  20;
    s[0] =   1;
    s[1] =   1;
    s[2] =   0;
    s[3] =   0;
    s[4] =   1;
    s[5] =   0;
    *k = 20;
  }
  else if ( *n_data == 3 )
  {
    *n = 7;
    v[0] = 70;
    v[1] = 20;
    v[2] = 39;
    v[3] = 37;
    v[4] =  7;
    v[5] =  5;
    v[6] = 10;
    w[0] = 31;
    w[1] = 10;
    w[2] = 20;
    w[3] = 19;
    w[4] =  4;
    w[5] =  3;
    w[6] =  6;
    s[0] =  1;
    s[1] =  0;
    s[2] =  0;
    s[3] =  1;
    s[4] =  0;
    s[5] =  0;
    s[6] =  0;
    *k = 50;
  }
  else if ( *n_data == 4 )
  {
    *n = 7;
    v[0] = 442;
    v[1] = 525;
    v[2] = 511;
    v[3] = 593;
    v[4] = 546;
    v[5] = 564;
    v[6] = 617;
    w[0] =  41;
    w[1] =  50;
    w[2] =  49;
    w[3] =  59;
    w[4] =  55;
    w[5] =  57;
    w[6] =  60;
    s[0] =   1;
    s[1] =   0;
    s[2] =   0;
    s[3] =   1;
    s[4] =   0;
    s[5] =   0;
    s[6] =   1;
    *k = 170;
  }
  else if ( *n_data == 5 )
  {
    *n = 8;
    v[0] = 350;
    v[1] = 400;
    v[2] = 450;
    v[3] =  20;
    v[4] =  70;
    v[5] =   8;
    v[6] =   5;
    v[7] =   5;
    w[0] =  25;
    w[1] =  35;
    w[2] =  45;
    w[3] =   5;
    w[4] =  25;
    w[5] =   3;
    w[6] =   2;
    w[7] =   2;
    s[0] =   1;
    s[1] =   0;
    s[2] =   1;
    s[3] =   1;
    s[4] =   1;
    s[5] =   0;
    s[6] =   1;
    s[7] =   1;
    *k = 104;
  }
  else if ( *n_data == 6 )
  {
    *n = 10;
    v[0] = 505;
    v[1] = 352;
    v[2] = 458;
    v[3] = 220;
    v[4] = 354;
    v[5] = 414;
    v[6] = 498;
    v[7] = 545;
    v[8] = 473;
    v[9] = 543;
    w[0] =  23;
    w[1] =  26;
    w[2] =  20;
    w[3] =  18;
    w[4] =  32;
    w[5] =  27;
    w[6] =  29;
    w[7] =  26;
    w[8] =  30;
    w[9] =  27;
    s[0] =   1;
    s[1] =   0;
    s[2] =   0;
    s[3] =   1;
    s[4] =   0;
    s[5] =   0;
    s[6] =   0;
    s[7] =   1;
    s[8] =   0;
    s[9] =   0;
    *k = 67;
  }
  else if ( *n_data == 7 )
  {
    *n = 10;
    v[0] = 92;
    v[1] = 57;
    v[2] = 49;
    v[3] = 68;
    v[4] = 60;
    v[5] = 43;
    v[6] = 67;
    v[7] = 84;
    v[8] = 87;
    v[9] = 72;
    w[0] = 23;
    w[1] = 31;
    w[2] = 29;
    w[3] = 44;
    w[4] = 53;
    w[5] = 38;
    w[6] = 63;
    w[7] = 85;
    w[8] = 89;
    w[9] = 82;
    s[0] =  1;
    s[1] =  1;
    s[2] =  1;
    s[3] =  1;
    s[4] =  0;
    s[5] =  1;
    s[6] =  0;
    s[7] =  0;
    s[8] =  0;
    s[9] =  0;
    *k = 165;
  }
  else if ( *n_data == 8 )
  {
    *n = 15;
    v[0]  = 135;
    v[1]  = 139;
    v[2]  = 149;
    v[3]  = 150;
    v[4]  = 156;
    v[5]  = 163;
    v[6]  = 173;
    v[7]  = 184;
    v[8]  = 192;
    v[9]  = 201;
    v[10] = 210;
    v[11] = 214;
    v[12] = 221;
    v[13] = 229;
    v[14] = 240;
    w[0]  =  70;
    w[1]  =  73;
    w[2]  =  77;
    w[3]  =  80;
    w[4]  =  82;
    w[5]  =  87;
    w[6]  =  90;
    w[7]  =  94;
    w[8]  =  98;
    w[9]  = 106;
    w[10] = 110;
    w[11] = 113;
    w[12] = 115;
    w[13] = 118;
    w[14] = 120;
    s[0]  =   1;
    s[1]  =   0;
    s[2]  =   1;
    s[3]  =   0;
    s[4]  =   1;
    s[5]  =   0;
    s[6]  =   1;
    s[7]  =   1;
    s[8]  =   1;
    s[9]  =   0; 
    s[10] =   0;
    s[11] =   0;
    s[12] =   0;
    s[13] =   1;
    s[14] =   1;
    *k = 750;
  }
  else if ( *n_data == 9 )
  {
    *n = 24;
    v[0]  =  825594;
    v[1]  = 1677009;
    v[2]  = 1676628;
    v[3]  = 1523970;
    v[4]  =  943972;
    v[5]  =   97426;
    v[6]  =   69666;
    v[7]  = 1296457;
    v[8]  = 1679693;
    v[9]  = 1902996;
    v[10] = 1844992;
    v[11] = 1049289;
    v[12] = 1252836;
    v[13] = 1319836;
    v[14] =  953277;
    v[15] = 2067538;
    v[16] =  675367;
    v[17] =  853655;
    v[18] = 1826027;
    v[19] =   65731;
    v[20] =  901489;
    v[21] =  577243;
    v[22] =  466257;
    v[23] =  369261;
    w[0]  =  382745;
    w[1]  =  799601;
    w[2]  =  909247;
    w[3]  =  729069;
    w[4]  =  467902;
    w[5]  =   44328;
    w[6]  =   34610;
    w[7]  =  698150;
    w[8]  =  823460;
    w[9]  =  903959;
    w[10] =  853665;
    w[11] =  551830;
    w[12] =  610856;
    w[13] =  670702;
    w[14] =  488960;
    w[15] =  951111;
    w[16] =  323046;
    w[17] =  446298;
    w[18] =  931161;
    w[19] =   31385;
    w[20] =  496951;
    w[21] =  264724;
    w[22] =  224916;
    w[23] =  169684;
    s[0]  =       1;
    s[1]  =       1;
    s[2]  =       0;
    s[3]  =       1;
    s[4]  =       1; 
    s[5]  =       1;
    s[6]  =       0;
    s[7]  =       0;
    s[8]  =       0;
    s[9]  =       1;
    s[10] =       1;
    s[11] =       0;
    s[12] =       1;
    s[13] =       0;
    s[14] =       0;
    s[15] =       1;
    s[16] =       0;
    s[17] =       0;
    s[18] =       0;
    s[19] =       0;
    s[20] =       0;
    s[21] =       1;
    s[22] =       1;
    s[23] =       1;
    *k = 6404180;
  }

  *n_data = *n_data + 1;

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

void subset_next_test ( )

//****************************************************************************80
//
//  Purpose:
//
//    subset_next_test() tests subset_next().
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    28 November 2024
//
//  Author:
//
//    John Burkardt
//
{
  int i;
  int j;
  int n = 5;
  int *s;

  cout << "\n";
  cout << "subset_next_test():\n";
  cout << "  Test subset_next()\n";
  cout << "\n";

  cout << "  Generate in order subsets of size " << n << "\n";
  cout << "\n";

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

  while ( true )
  {
    i = i + 1;
    cout << "  " << setw(2) << i << ":";
    for ( j = 0; j < n; j++ )
    {
      cout << "  " << s[j];
    }
    cout << "\n";

    subset_next ( n, s );

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

  delete [] s;

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

void timestamp ( )

//****************************************************************************80
//
//  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:
//
//    19 March 2018
//
//  Author:
//
//    John Burkardt
//
{
# define TIME_SIZE 40

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

  now = std::time ( NULL );
  tm_ptr = std::localtime ( &now );

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

  std::cout << time_buffer << "\n";

  return;
# undef TIME_SIZE
}