C ++ class implementation of any scale assignment

One. Assign problem

In life, I often meet this problem, have n personal completion, this n individual completes the efficiency of the tasks (or the time required), so that the assignment is a problem that the assignment is to complete which task, this type The problem is called assignment issues or dispatch issues.

1. Mathematical model assigned to the problem

Introducing Variables Xij, which can only be 1 or 0, and let Xij = 1 represents the assignment of the i person to complete the JU task xij = 0 means that the i-I person does not assign the second task; when the problem requires extremely small When the mathematical model is: MIN Z =

1

2

3

4

Constraint Conditions 2 Description J Item The JUNT can only be completed by 1 person; constraints 3 illustrate that the i person can only complete one task. The solution to the constraints 2 - 4 can be satisfied, and the matrix can be expressed in the matrix, which is called a solution matrix.

When the problem requires extremely large, Bij = M-Cij can be converted into a polarization model.

two. Solution method assigned

Assignment issues are the special cases of the 0-1 planning, and the special case of transportation issues, can be solved with integer planning, 0-1 planning, transportation issues, but because ignore the particularity of the assignment, therefore cannot achieve good solution efficiency .

The optimal solution for assigning problems has this nature. If the minimum element of the row (column) is subtracted from a line (column) of the coefficient matrix (column), the new matrix (Bij ') is obtained, then (Bij ') The optimal solution obtained by the coefficient matrix and the optimal solution obtained with the original coefficient matrix.

Kunen proposed a solution to the issue of assignment issues in 1955, which cited the Corghig's aimation of 0 elements in the matrix: the maximum number of independent 0 elements in the coefficient matrix is ​​equal to the minimum number of straight numbers that can override all 0 elements.

three. Program implementation

According to the above method, the ASSIGNMENT class is prepared to achieve a resolution of an assignment issue for any scale.

Class Assignment

{

PUBLIC:

Assignment (INT N, INT * EFF);

~ Assignment ();

INT * GetAssignment (bool ismin = true);

Private:

Bool Hasassigned (INT * EFF);

Bool Haszero (INT * EFF);

Void changeMintomax ();

Void getRowColzero (INT * EFF);

Void Assignandgetoff (INT * EFF);

Void Changeefficiency (INT * EFF);

Void gettaskassignment (int * EFF);

Void AssignCore; "INT * EFF);

Void RESETZERO (INT * EFF);

INT getLinenum (INT * EFF);

Private:

Bool allassigned;

INT * TASK;

INT * Efficiency;

Int scale;

Int * rowticked;

Int * coolicked;

PUBLIC: / / Several constants defined

Const int maxvalue;

Const Bool Maxassign;

Const bool minassign;

Const int assigned;

Const int getoffed;

}

Assignment class description

1.Assignment class implementation task assignment; 2. Example of use

Assignment assignment = assignment (n, eff);

INT * TASK = Assignment.gettaskassignment (ismin);

Where n represents the number of assignments;

The EFF efficiency coefficient is transmitted in one-dimensional array;

Is ISMIN Take a minimum price assignment; ismin = true, expressed as the minimum price assignment, default, ismin = true;

TASK assignment results, if Task [i] = j, indicating that the i-th person completes the JU task (with 0 is the first order);

3. Application example:

int main ()

{

int Scale, * EFF, * TASK

INT I, J;

// Get Scale

Cout << "/ NTHE Scale of Problem:"

CIN >> Scale;

// construct eff

EFF = new int [scale * scale];

// Get Efficiency

For (i = 0; i

For (j = 0; j

{

Cout << "/ nthe effectiency of the" << i 1 << "th Person doing the"

<< J 1 << "TH task is (Natural Number):";

CIN >> EFF [i * scale j];

}

// Get minormax

Bool ismin = true;

CHAR ISY;

COUT << "/ NIS A MIN COST Assignment? (y for yes, & tahers for no):";

CIN >> ISY;

ISMIN = (isy == 'y' || isy == 'y');

// List the efficience

COUT << "/ n" << "The effiencience:";

For (i = 0; i

{

COUT << "/ nthe" << i 1 << "TH PERSON:"

For (j = 0; j

COUT << EFF [i * scale j] << "

}

// Assignment Type

IF (ismin)

COUT << "/ n / nmin cost assignment./N";

Else

Cout << "/ n / nmax effect assignment./n";

Assignment assignment = assignment (scale, (int *) EFF);

Task = assignment.getassignment (ismin);

// Output the result

For (i = 0; i

COUT << "/ nthe" << i 1 << "th Person do the" << Task [i] 1 << "TH task;"; cout << "/ n";

Return 0;

}

The results can be output by prompting the size of the problem, the corresponding efficiency matrix, solving method (maximum efficiency or minimum).

The following is the content of assignment.cpp, the content of Assignment.h, is a class defined section.

#include "assignment.h"

Assignment :: Assignment: maxValue (65532), maxssign (false), minassign (true), assigned (-1), getoffed (-2) {scale = n; effectiency = new int [scale * scale]; for (int i = 0; i

Rowticked = new int [scale]; coldicked = new int [scale]; task = new int [scale];} assignment :: ~ assignment () {delete [] effect; delete [] rowticked; delete [] cool; delete [ ] Task;}

INT * Assignment :: GetAssignment (Bool ismin) {if (! ismin) ChangeMintomax ();

Allassigned = false;

GetRowColzero (Efficiency); Assignandgetoff (efficiency);

Assigncore (Efficiency);

Return Task; // Task is set by associgncore ()}

Void Assignment :: changeMintomax () {int max = 0, i, j; // get max for (i = 0; i max) max = effect [i * scale j]; // change for (i = 0; i

Void Assignment :: GETROWCOLZERO (INT * EFF) {INT I, J, Min; // Zero in row for (i = 0; i

Void Assignment :: Assignandgetoff (int * EFF) {Int i, j, k, rowzero, colzero, zeropos; bool isover = false; while (! isover) {isover = true; // from row Which Has Only One Zero for i = 0; i

IF (Allassigned) Return; if (Haszero (EFF)) {for (i = 0; i

INT assignment :: getLinenum (int * EFF) {INT I, J, LINENUM = 0; BOOL HASMORE = true; // = 0; i

) EFF [i * scale j] - = minValue; for (j = 0; j