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

# include "knapsack_brute.h"

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

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:

    25 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 = ( int * ) malloc ( n * sizeof ( int ) );
  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;
    }

  }

  free ( s_test );

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

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

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

int i4vec_sum ( int n, int a[] )

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

    29 May 2003

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

void subset_next ( int n, int *s )

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

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