optimal.h

eC++编译器源码

#pragma Optimal

/* This module provides the procedure Try which solves the problem of optimizing
   the subset of objects to be packed so as to maximixe their value without exceeding the weight limit.
   The arguments of this procedure :
       object   .......... is a o-origin array of RECORD type Object.
       maxValue .......... is the maximum value optained for an object step.
       optimalSolution ... is a BOOLEAN array  which  contain TRUE for each 
                           weight\value used to get the object step optimal
                           solution.
       numberOfObjects ... is the number of objects.
       weightLimit ....... is the limit of the weight which must not be
                           exceeded when finding the optimal solution.
   The procedure Marry generates a male-optimal solution to the stable
   marriage problem.  Each man provides a ranking for each woman in a NxN matrix
   and each woman does the same.  If the input is stored in a two-dimensional
   MxM matrix then M must be passed in too since matrix is converted to a vector.
   The output is a list of the wives if a solution can be found (TRUE). 
*/
typedef
   struct {
                 unsigned int value, weight;
   } Object;

void 
   Try(Object /*in*/ &object[], unsigned int /*out*/ &maxValue, 
                               boolean /*out*/ &optimalSolution[], 
                               /*in*/ unsigned int numberOfObjects,
                               /*in*/unsigned int weightLimit);
boolean Marry(unsigned int /*in*/&men[], unsigned int &women[], unsigned int M, unsigned int N, unsigned int /*out*/ &wives[]);
#if defined(FOO)
#include <Optimal.h>
#include <HexDump.h>
void main()
{
Object x[10];
boolean b[20];
unsigned int out;
unsigned int women[2][2],men[2][2],xx[6];
  x[0].value = 15;  x[0].weight = 8;
  x[1].value = 5;  x[1].weight = 5;
  x[2].value = 12;  x[2].weight = 7;
  x[3].value = 4;  x[3].weight = 9;
  x[4].value = 15;  x[4].weight = 5;
  Try(x, out, b, 5, 20);
  Dump(out);
  Dump(b);
  men[0][0] = 2;  men[0][1] = 1;    /*both like 2 best*/
  men[1][0] = 2;  men[1][1] = 1;
  women[0][0] = 2;  women[0][1] = 1;  /*she likes 2*/
  women[1][0] = 1;  women[1][1] = 2;  /*she likes 1*/
  if (Optimal.Marry(men,women,2,2,xx)) ;
  Dump(xx);
  };
#endif