help for writing an algorithm

I am doing designing an algorithm for an assignment, and I am not sure that I have written a correct algorithm, would you please guide me? The question is: There are n student S1, S2, …, Sn and and n grade: G1,G2,…Gn. Each student must be assigned to exactly one grade and exactly one student is assigned to any one grade. If Tij is the value of assigning Si to Gj, I must find the Q subset of T which is maximum. (I must assign workers to the best possible job) An example for this question is if I have two student S1 and S2 and also I have 2 Grades G1 and G2, I have for example the T12= 12, T21=7, T11=9, T22=16 the subset must be Q={T12, T22} I have written the following algorithm (in java) :

   Algorithm studentG(J[],W[],V[][],x[][])
 {
     // I use heap data structure for solving this problem
     // initial all x[][] = 0
      ArrayList<Heap> students = new ArrayList<Heap>();
      students = Heap(v[][]); // this method make a heap for each student,

     for(int k = 0; k< J.l开发者_StackOverflow社区ength, k++)
   {
  Boolean test = false;
  // this loop is for each student to assign each student to only one grade not more.
  for(int m = 0; m< students.size(); m++)
 {
If(students.get[m].root.getGrade() ==k && test == false){
test = true;
//I have assigned 1 to the feasible and 0 othrwise
 x[m][k] = 1;
}else if(students.get[m].root. getGrade() != k){
 Continue;
}else if(students.get[m].root. getGrade() == k && test == true){
 students.get[m].remove(root);
 students.get[m].heapify();
 }
}
}

Does this work good? Thanks.

What you are trying to solve is actually a rephrasing of the travelling salesman problem and Google will give you lots of possible algorithms to solve it.

Your algorithm does nothing bu assigning grades, there is no optimisation. You might as well take the grades and students in order and simply assign each one to the other one. This will produce a possible set for the solution but it will (might, 1 chance out of ) not be optimal.

Before implementing an algorithm, try to express it in pseudo-language terms. A trivial implementation of the algorithm could look like this:

foreach student S do
  foreach unassigned grade G do
    Add {G, S} to the solutions
    Compute the solution score
    If (this score > greater score so far) Then 
      Keep solution like this
      Mark G as assigned
    Else 
      Remove {G, S} from the solution
  Next
Next

As far as data structures go, you could have in Java:

// The number of grades and students
public static final int N = 10;

// The students and grades are just a suite of numubers
List<int> students = new ArrayList<int>(N);
List<int> grades = new ArrayList<int>(N);    
for (int i=0; i<N; ++i) {
  students.set(i, i);
  grades.set(i, i);
}

// Each score for a possible pair of grade student is stored in a matrix 
int[][] scores = new int[N][N];
for (int s=0; s<N; ++s) {
  for (int g=0; g<N; ++g) {
    scores[s][g] = students.get(s) * grades.get(g);
  }
}

// An association of student and grade
class Association {
  int student;
  int grade;
  int score;
  public Association(int student, int grade, int score) {
    this.student = student;
    this.grade = grade;
    this.score = score;
  }
}

// The solution
Stack<Association> solution = new Stack<Association>(N);

I'll let you try to implement the algorithm above with those data structures, using Stack.push and Stack.pop to add/remove an association from the solution and List.remove to mark a grade as used in the solution.

Don't forget to implement a function that computes the sum of the scores in the current solution (could be somthing like: public int getSolutionScore(Stack solution))

@Samuel: "Each student must be assigned to exactly one grade and exactly one student is assigned to any one grade."

Which means having a function that maps a student to any grade S->G. The condition does not seem to introduce side constraints (i.e. all grades must be assigned in best way among the set of students while maintaining the 1-to-1 constraint.)

So in essence (if the problem was really formulated correctly) this means simply chosing

Q = argmax_j(Tij) for all i's.

Which is simply the maximum value of each row of the cost matrix T .

I guess i dont have to provide a code example since finding the maximum element is a rather trivial operation of O(n). Use heaps if you want, but a simple scanning and keeping the max will also work.

Since this seems too simple, the problem might have been formulated incorrectly.

Your example is unclear. Doesn't selecting T12 and T22 violate your conditions (i.e. there are two students assigned to Grade 2).