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

# include "knapsack_rational.h"

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

void knapsack_rational ( int n, double mass_limit, double p[], double w[],
  double x[], double *mass, double *profit )

/******************************************************************************/
/*
  Purpose:

    knapsack_rational() solves the rational knapsack problem.

  Discussion:

    The rational knapsack problem is a generalization of the 0/1 knapsack
    problem.  It is mainly used to derive a bounding function for the
    0/1 knapsack problem.

    The 0/1 knapsack problem is as follows:

      Given:
        a set of N objects,
        a profit P(I) and weight W(I) associated with each object,
        and a weight limit MASS_LIMIT,
      Determine:
        a set of choices X(I) which are 0 or 1, that maximizes the profit
          P = Sum ( 1 <= I <= N ) P(I) * X(I)
        subject to the constraint
          Sum ( 1 <= I <= N ) W(I) * X(I) <= MASS_LIMIT.

    By contrast, the rational knapsack problem allows the values X(I)
    to be any value between 0 and 1.  A solution for the rational knapsack
    problem is known.  Arrange the objects in order of their "profit density"
    ratios P(I)/W(I), and then take in order as many of these as you can.
    If you still have "room" in the weight constraint, then you should
    take the maximal fraction of the very next object, which will complete
    your weight limit, and maximize your profit.

    If should be obvious that, given the same data, a solution for
    the rational knapsack problem will always have a profit that is
    at least as high as for the 0/1 problem.  Since the rational knapsack
    maximum profit is easily computed, this makes it a useful bounding
    function.

    This routine assumes that the objects have already been
    arranged in descending order of the "profit density".

    This can be done by a call to knapsack_rational().

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    16 November 2024

  Author:

    John Burkardt

  Reference:

    Donald Kreher, Douglas Simpson,
    Combinatorial Algorithms,
    CRC Press, 1998,
    ISBN: 0-8493-3988-X,
    LC: QA164.K73.

  Input:

    int N, the number of objects.

    double MASS_LIMIT, the weight limit of the chosen objects.

    double P[N], the "profit" or value of each object.
    The entries of P are assumed to be nonnegative.

    double W[N], the "weight" or cost of each object.
    The entries of W are assumed to be nonnegative.

  Output:

    double X[N], the choice function for the objects.
    0.0, the object was not taken.
    1.0, the object was taken.
    R, where 0 < R < 1, a fractional amount of the object was taken.

    double *MASS, the total mass of the objects taken.

    double *PROFIT, the total profit of the objects taken.
*/
{
  int i;

  *mass = 0.0;
  *profit = 0.0;

  for ( i = 0; i < n; i++ )
  {
    if ( mass_limit <= *mass )
    {
      x[i] = 0.0;
    }
    else if ( *mass + w[i] <= mass_limit )
    {
      x[i] = 1.0;
      *mass = *mass + w[i];
      *profit = *profit + p[i];
    }
    else
    {
      x[i] = ( mass_limit - *mass ) / w[i];
      *mass = mass_limit;
      *profit = *profit + p[i] * x[i];
    }
  }
  return;
}
/******************************************************************************/

void knapsack_reorder ( int n, double p[], double w[] )

/******************************************************************************/
/*
  Purpose:

    knapsack_reorder() reorders the knapsack data by "profit density".

  Discussion:

    This routine must be called to rearrange the data before calling
    routines that handle a knapsack problem.

    The "profit density" for object I is defined as P(I)/W(I).

    On return, the objects have been sorted so that profits and weights 
    are in descending order of profit density.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    16 November 2024

  Author:

    John Burkardt

  Reference:

    Donald Kreher, Douglas Simpson,
    Combinatorial Algorithms,
    CRC Press, 1998,
    ISBN: 0-8493-3988-X,
    LC: QA164.K73.

  Input:

    int N, the number of objects.

    double P[N], the "profit" or value of each object.

    double W[N], the "weight" or cost of each object.

  Output:

    double P[N], the "profit" or value of each object after sorting.

    double W[N], the "weight" or cost of each object after sorting.
*/
{
  int i;
  int j;
  double t;
/*
  Rearrange the objects in order of "profit density".
*/
  for ( i = 0; i < n; i++ )
  {
    for ( j = i + 1; j < n; j++ )
    {
      if ( p[i] * w[j] < p[j] * w[i] )
      {
        t    = p[i];
        p[i] = p[j];
        p[j] = t;

        t    = w[i];
        w[i] = w[j];
        w[j] = t;
      }
    }
  }
  return;
}