我正在为一项作业设计算法,但我不确定我写的算法是否正确,您能指导我吗?问题是:有n个学生S1,S2,…,Sn和n级: G1,G2,…Gn。每个学生必须被分配到恰好一个年级,并且恰好一个学生被分配到任何一个年级。如果Tij是将Si赋值给Gj的值,我必须找到T的Q子集,它是最大的。(我必须将工人分配到可能的最佳工作)这个问题的一个例子是,如果我有两个学生S1和S2,还有两个年级G1和G2,我有例如T12= 12,T21=7,T11=9,T22=16子集必须是Q={T12,T22}我写了以下算法(在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.length, 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();
}
}
}这样做效果好吗?谢谢。
发布于 2010-12-12 15:27:49
你正在尝试解决的实际上是travelling salesman problem的改写,谷歌会给你很多可能的算法来解决它。
你的算法除了分配分数什么都不做,没有优化。你不妨将成绩和学生按顺序排列,然后简单地将它们分配给另一个。这将为解决方案产生一个可能的集合,但它(可能,1次机会)不是最优的。
在实现算法之前,试着用伪语言来表达它。该算法的简单实现可能如下所示:
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就数据结构而言,您可以在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);我将让您尝试使用这些数据结构实现上面的算法,使用Stack.push和Stack.pop在解决方案中添加/删除关联,使用List.remove标记解决方案中使用的等级。
不要忘记实现一个函数来计算当前解决方案中得分的总和(可能类似于: public int getSolutionScore(堆栈解决方案))
发布于 2011-06-28 20:32:47
@Samuel:“每个学生必须被分配到一个年级,并且恰好有一个学生被分配到任何一个年级。”
这意味着有一个将学生映射到任何年级S->G的函数。该条件似乎不会引入副作用约束(即,必须以最佳方式在学生集合中分配所有成绩,同时保持1对1的约束。)
因此,本质上(如果问题确实被正确地表述),这意味着简单地选择
对于所有i's,Q = argmax_j(Tij)。
其仅仅是成本矩阵T_的每一行的最大值。
我想我不必提供代码示例,因为寻找最大元素是O(n)的一个相当琐碎的操作。如果您愿意,可以使用堆,但简单的扫描和保留最大值也可以。
由于这看起来太简单了,这个问题可能被错误地表述了。
发布于 2010-12-12 15:27:12
你的例子不清楚。选择T12和T22不会违反您的条件(即有两个学生分配到二年级)。
https://stackoverflow.com/questions/4420662
复制相似问题