function [ vmax, wmax, smax ] = knapsack_brute ( n, v, w, k )

%*****************************************************************************80
%
%% 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.
%
%    real v[n], w[n]: the value and weight of each item.
%
%    real k: the maximum weight capacity of the knapsack.
%
%  Output:
%
%    real vmax: the total value of the items in the knapsack.
%
%    real 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.
%
  vmax = 0.0;
  wmax = 0.0;
  smax = zeros ( n, 1 );

  s_test = zeros ( n, 1 );
  
  while ( true )

    w_test = ( s_test' * w );

    if ( w_test <= k )

      v_test = ( s_test' * v );

      if ( vmax < v_test )
        smax = s_test;
        vmax = v_test;
        wmax = w_test;
      end

    end

    s_test = subset_next ( s_test );
    if ( sum ( s_test ) == 0 )
      break;
    end

  end

  return
end
