院校考试部分配学生考试时间(基于贪心算法)

文章背景

        院校考试部需要为学生安排考试时间。要求同时选择两门课的学生，不能同时考两门课。
        现有课程关系如下图所示

​        现有学生选课信息如下图所示

​ 现在有学生选课信息和课程关系图，该如何解决呢？

​ 先建立课程关系邻接矩阵，再建立一个·空的课程矩阵。看着学生选课信息，往空课程矩阵里添值，添什么值，就需要看课程关系邻接矩阵。若矩阵里权值为0的边，就不往空矩阵里添，反之添加。

代码实现

建立课程关系邻接矩阵

可参考▶基于邻接矩阵表示课程关系（Java）

空矩阵添权值逻辑

   public AMatrix IdentifyNodeInMatrix(int[] arr, AMatrix AMatrix) {
        AMatrix temp = new AMatrix(7);
        String[] labels = {"CSCI203", "CSCI204", "CSCI205", "CSCI212", "CSCI213", "CSCI222", "CSCI235"};
        for (String label : labels) {
            temp.insertVertex(label);//插入结点
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < labels.length; j++) {
//                System.out.println(arr[i]+""+ arr[j]);
//                System.out.println(AMatrix.getWeight(arr[i], arr[j]));
                //权值不为0
                if (AMatrix.getWeight(arr[i], j) != 0 || AMatrix.getWeight(j, arr[i]) != 0) {
//                    System.out.println("有权值"+arr[i]+""+ j);
                    temp.insertEdge(arr[i], j, 1);
                    temp.insertEdge(j, arr[i], 1);

                }


                //权值为0
                if (AMatrix.getWeight(arr[i], j) == 0 || AMatrix.getWeight(j, arr[i]) == 0) {
//                    System.out.println("无权值"+arr[i]+""+ j);


                    temp.insertEdge(arr[i], j, 0);
                    temp.insertEdge(j, arr[i], 0);
                }


            }
        }
        return temp;
    }

    public int[][] newArrayOfNonNodes(int[][] array, int[][] array1) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (i == j) {
                    array[i][j] = 1;
                    array[j][i] = 1;
                }

                if ((array[i][j] == 0 && array1[i][j] == 0) | (array[j][i] == 0 && array1[j][i] == 0)) {
                    array[i][j] = 0;
                    array[j][i] = 0;
                } else {
                    array[i][j] = 1;
                    array[j][i] = 1;
                }

            }
        }
        return array;
    }

   

计数权值为0边

 public int[][] newArrayOfNonNodes1(int[][] array, int[][] array1, int[][] array2) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                if (i == j) {
                    array[i][j] = 1;
                    array[j][i] = 1;
                }

                if ((array[i][j] == 0 && array1[i][j] == 0 && array2[i][j] == 0) | (array[j][i] == 0 && array1[j][i] == 0 && array2[i][j] == 0)) {
                    array[i][j] = 0;
                    array[j][i] = 0;
                } else {
                    array[i][j] = 1;
                    array[j][i] = 1;
                }
            }
        }
        return array;
    }

课程信息排序

private static List<Map.Entry<String, Integer>> mapValueSort(HashMap<String, Integer> labelsMap) {
    List<Map.Entry<String, Integer>> list = new ArrayList<Map.Entry<String, Integer>>(labelsMap.entrySet());

    list.sort(new Comparator<Map.Entry<String, Integer>>() {
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            return o1.getValue() < o2.getValue() ? 1 : ((o1.getValue() == o2.getValue()) ? 0 : -1);
        }
    });
    return list;


}

主函数

  public static void main(String[] args) {
        //txt数据
        int total = 5;
        String[] Belinda = {"CSCI212", "CSCI235", "CSCI222", "CSCI203"};
        int[] Belinda1 = {3, 6, 5, 0};
        String[] Calvin = {"CSCI205", "CSCI204", "CSCI222"};
        int[] Calvin1 = {2, 1, 5};
        String[] Johnathan = {"CSCI212", "CSCI222", "CSCI204", "CSCI203"};
        int[] Johnathan1 = {3, 5, 1, 0};
        String[] Brandon = {"CSCI212", "CSCI203", "CSCI235", "CSCI213"};
        int[] Brandon1 = {3, 0, 6, 4};

        int[][] totalarray = new int[7][7];
        mainFuction mainFuction = new mainFuction();
        AMatrix aMatrix = mainFuction.createAMatrix();

        AMatrix aMatrix1 = mainFuction.IdentifyNodeInMatrix(Belinda1, aMatrix);
        int[][] Belinda1edges = aMatrix1.getedgescollection();

        AMatrix aMatrix2 = mainFuction.IdentifyNodeInMatrix(Calvin1, aMatrix);
        int[][] Calvin1edges = aMatrix2.getedgescollection();
        AMatrix aMatrix3 = mainFuction.IdentifyNodeInMatrix(Johnathan1, aMatrix);
        int[][] Johnathan1edges = aMatrix3.getedgescollection();
        AMatrix aMatrix4 = mainFuction.IdentifyNodeInMatrix(Brandon1, aMatrix);
        int[][] Brandon1edges = aMatrix4.getedgescollection();

        int[][] num1 = mainFuction.newArrayOfNonNodes(totalarray, Belinda1edges);
        int[][] num2 = mainFuction.newArrayOfNonNodes1(totalarray, num1, Brandon1edges);
        int[][] num3 = mainFuction.newArrayOfNonNodes1(totalarray, num2, Calvin1edges);
        int[][] num4 = mainFuction.newArrayOfNonNodes1(totalarray, num3, Johnathan1edges);


        String[] labels = {"CSCI203", "CSCI204", "CSCI205", "CSCI212", "CSCI213", "CSCI222", "CSCI235"};

        int[] arrcount0 = new int[7];
        for (int i = 0; i < num4.length; i++) {
            for (int j = 0; j < num4.length; j++) {
                if (num4[i][j] == 0) {
                    arrcount0[i] += 1;
                }

            }
        }



        HashMap<String, Integer> hashMap = new HashMap<String, Integer>();
        for (int i = 0; i < arrcount0.length; i++) {
            hashMap.put(labels[i], arrcount0[i]);
        }
        List<Map.Entry<String, Integer>> list = mapValueSort(hashMap);

        System.out.println("Slot 1:" + "," + list.get(0).getKey() + "," + list.get(1).getKey() + "       " + "3");
        if (aMatrix.getWeight(1, 6) != 0) {
            System.out.println("Slot 2:" + "," + list.get(3).getKey() + "," + list.get(6).getKey() + "       " + "3");
        }
        if (aMatrix.getWeight(4, 2) != 0) {
            System.out.println("Slot 3:" + "," + list.get(4).getKey() + "," + list.get(5).getKey() + "       " + "3");
        }
        System.out.println("Slot 4:" + "," + list.get(2).getKey() + "               " + "3");
}
}