# include <cstdlib>

using namespace std;

# include "knapsack_brute.hpp"

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

void knapsack_brute ( int n, int *v, int *w, int k, int &vmax, int &wmax, 
  int *smax )

//*****************************************************************************/
//
//  Purpose:
//
//    knapsack_brute() seeks a solution of the knapsack problem.
//
//  Discussion:
//
//    N valuable items are available, each with given value V and weight W.
//
//    A thief's knapsack can carry no more than K pounds.  
//
//    The thief seeks a selection S of items to carry in the knapsack 
//    of maximum total value.
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    28 November 2024
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    integer n: the number of items.
//
//    integer v[n], w[n]: the value and weight of each item.
//
//    integer k: the maximum weight capacity of the knapsack.
//
//  Output:
//
//    integer vmax: the total value of the items in the knapsack.
//
//    integer wmax: the total weight of the items in the knapsack.
//
//    integer smax[n]: a vector of 0's and 1's, indicating which items
//    were selected.
//
{
  int i;
  int *s_test;
  int v_test;
  int w_test;

  vmax = 0;
  wmax = 0;
  for ( i = 0; i < n; i++ )
  {
    smax[i] = 0;
  }

  s_test = new int[n];
  for ( i = 0; i < n; i++ )
  {
    s_test[i] = 0;
  }
  
  while ( true )
  {
    w_test = i4vec_dot_product ( n, s_test, w );

    if ( w_test <= k )
    {
      v_test = i4vec_dot_product ( n, s_test, v );

      if ( vmax < v_test )
      {
        for ( i = 0; i < n; i++ )
        {
          smax[i] = s_test[i];
        }
        vmax = v_test;
        wmax = w_test;
      }

    }

    subset_next ( n, s_test );

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

  }

  delete [] s_test;

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

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

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

int i4vec_sum ( int n, int a[] )

//****************************************************************************80
//
//  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:
//
//    26 May 1999
//
//  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;
}
//****************************************************************************80

void subset_next ( int n, int *s )

//****************************************************************************80
//
//  Purpose:
//
//    subset_next() returns the next subset of n items.
//
//  Discussion:
//
//    The subset is represented as a vector of binary digits.
//    The subsets are listed in numerical order.
//    After the last subset is returned, the sequence begins again at 0.
//
//  Example:
//
//    [ 0, 0, 0 ]
//    [ 0, 0, 1 ]
//    [ 0, 1, 0 ]
//    [ 0, 1, 1 ]
//    [ 1, 0, 0 ]
//    [ 1, 0, 1 ]
//    [ 1, 1, 0 ]
//    [ 1, 1, 1 ]
//
//  Licensing:
//
//    This code is distributed under the MIT license.
//
//  Modified:
//
//    29 November 2024
//
//  Author:
//
//    John Burkardt
//
//  Input:
//
//    integer n: the size of the subset.
//
//    integer s[n]: the current subset.
//
//  Output:
//
//    integer s[n]: the next subset.
//
{
  int i;
//
//  Starting at the last index, add 1, and if necessary, carry to the left.
//
  for ( i = n - 1; 0 <= i; i-- )
  {
    if ( s[i] == 0 )
    {
      s[i] = 1;
      break;
    }
    else
    {
      s[i] = 0;
    }

  }

  return;
}