首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >编写算法的帮助

编写算法的帮助
EN

Stack Overflow用户
提问于 2010-12-12 15:12:48
回答 3查看 1.5K关注 0票数 0

我正在为一项作业设计算法,但我不确定我写的算法是否正确,您能指导我吗?问题是:有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中):

代码语言:javascript
复制
   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();
 }
}
}

这样做效果好吗?谢谢。

EN

回答 3

Stack Overflow用户

发布于 2010-12-12 15:27:49

你正在尝试解决的实际上是travelling salesman problem的改写,谷歌会给你很多可能的算法来解决它。

你的算法除了分配分数什么都不做,没有优化。你不妨将成绩和学生按顺序排列,然后简单地将它们分配给另一个。这将为解决方案产生一个可能的集合,但它(可能,1次机会)不是最优的。

在实现算法之前,试着用伪语言来表达它。该算法的简单实现可能如下所示:

代码语言:javascript
复制
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中使用:

代码语言:javascript
复制
// 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(堆栈解决方案))

票数 2
EN

Stack Overflow用户

发布于 2011-06-28 20:32:47

@Samuel:“每个学生必须被分配到一个年级,并且恰好有一个学生被分配到任何一个年级。”

这意味着有一个将学生映射到任何年级S->G的函数。该条件似乎不会引入副作用约束(即,必须以最佳方式在学生集合中分配所有成绩,同时保持1对1的约束。)

因此,本质上(如果问题确实被正确地表述),这意味着简单地选择

对于所有i's,Q = argmax_j(Tij)。

其仅仅是成本矩阵T_的每一行的最大值。

我想我不必提供代码示例,因为寻找最大元素是O(n)的一个相当琐碎的操作。如果您愿意,可以使用堆,但简单的扫描和保留最大值也可以。

由于这看起来太简单了,这个问题可能被错误地表述了。

票数 0
EN

Stack Overflow用户

发布于 2010-12-12 15:27:12

你的例子不清楚。选择T12和T22不会违反您的条件(即有两个学生分配到二年级)。

票数 -1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/4420662

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档