当前位置: 首页 > 面试题库 >

参与者人数为奇数的每周小组分配算法

施阎宝
2023-03-14
问题内容

对于我之前提出的问题,有一个循环解决方案。它适用于偶数人员,但是一旦实施算法并对其进行尝试,所有建议都将失效。我尝试了许多变体,((将最后一个和其他一群人分组,第二个小组最后一个小组,不同的组合,第二行和第四行到最后一行的最后一行,我认为这会给我最大的收获)最佳解决方案,但仍然有很多重复项)。有人可以提出一条可行的解决方案,还是一个证明,如果没有两个人在一起工作超过一次,就无法找到解决方案,那么我就可以停止尝试使之工作。如果您想要用Java实现的算法,我可以发布它,以便您可以使用它。

谢谢。


问题答案:

23名2人和1人3组的学生14周的时间不足,因此本地搜索能够找到解决方案。

 18  1 11|  3  4|  5  7|  9  6|  0 17|  2 12| 10 19| 15 16| 21  8| 14 20| 13 22|
  6 13 18| 17  4|  5  0| 20  1| 12 11| 10  9|  2 14| 15  7|  3  8| 19 16| 21 22|
 21 17  7| 19 22|  3  1|  2  8|  0 10| 14 12| 13 11|  6 16|  5 15| 18 20|  9  4|
  8  1 13| 18  2|  6 11| 20  0| 12 10| 14 15|  5 17|  9 21|  4 19|  3 22| 16  7|
  0  4 16| 17 20| 21  3|  7 18| 13 19|  1  5|  9 11| 15  2| 14  8| 10  6| 12 22|
 12  1 17| 15  4|  8  6| 16 18|  9  0| 11 22|  5 14|  3  2|  7 13| 19 20| 21 10|
  4  1 22| 12  8| 15  6|  7  0|  9 17| 11  3| 13  2|  5 18| 10 14| 19 21| 20 16|
  0  1  6| 13 21| 15 12| 17  8| 20 10| 11  4|  3 14|  5 16|  7  2| 19  9| 18 22|
 13 16  3|  2  9| 11 20|  6 17| 22 10|  5 12|  0 14| 15  1|  8 18| 19  7| 21  4|
 14  1  7|  2  4|  5  9|  3  6|  8 10| 13 12| 21  0| 17 16| 22 20| 19 18| 11 15|
 14 18 21| 12  4|  5  6|  2 19|  8 20|  1  9| 13  0| 11 16| 17 15|  3 10|  7 22|
 21  6  2|  3 20|  5 13| 16  8| 18 17|  0 12| 22 14| 10  1|  9 15|  7  4| 11 19|
  0 11  2|  6  4| 16 14|  7  8| 17 10|  1 19| 13  9|  3 18| 21 12| 20  5| 15 22|
  1 16  2| 14 13|  3  7|  8  4| 11 10|  9 12|  0 18| 15 19| 17 22|  6 20| 21  5|

这是实现它的Java代码。

public class Schedule {
  private final int weekCount;
  private final int groupCount;
  private final int personCount;
  private final int groupFirstSlot[];
  private final int weekSlotPerson[][];

  public Schedule(int weekCount, int groupCount, int personCount) {
    this.weekCount = weekCount;
    this.groupCount = groupCount;
    this.personCount = personCount;
    int remainingPersonCount = personCount;
    this.groupFirstSlot = new int[groupCount + 1];
    for (int remainingGroupCount = groupCount;
         remainingGroupCount > 0;
         remainingGroupCount--) {
      groupFirstSlot[remainingGroupCount] = remainingPersonCount;
      remainingPersonCount -= remainingPersonCount / remainingGroupCount;
    }
    this.weekSlotPerson = new int[weekCount][personCount];
    for (int week = 0; week < weekCount; week++) {
      for (int person = 0; person < personCount; person++) {
        weekSlotPerson[week][person] = person;
      }
    }
  }

  public int getWeekCount() {
    return weekCount;
  }

  public int getGroupCount() {
    return groupCount;
  }

  public int getPersonCount() {
    return personCount;
  }

  public int getGroupFirstSlot(int group) {
    return groupFirstSlot[group];
  }

  public int getWeekSlotPerson(int week, int slot) {
    return weekSlotPerson[week][slot];
  }

  public void swapWeekSlotPerson(int week, int slotOne, int slotTwo) {
    int temp = weekSlotPerson[week][slotOne];
    weekSlotPerson[week][slotOne] = weekSlotPerson[week][slotTwo];
    weekSlotPerson[week][slotTwo] = temp;
  }

  public int getConflictCount() {
    int pairCount[][] = new int[personCount][personCount];
    for (int week = 0; week < weekCount; week++) {
      for (int group = 0; group < groupCount; group++) {
        for (int slotOne = groupFirstSlot[group];
             slotOne < groupFirstSlot[group + 1];
             slotOne++) {
          int personOne = weekSlotPerson[week][slotOne];
          for (int slotTwo = groupFirstSlot[group];
               slotTwo < groupFirstSlot[group + 1];
               slotTwo++) {
            int personTwo = weekSlotPerson[week][slotTwo];
            pairCount[personOne][personTwo]++;
          }
        }
      }
    }
    int conflictCount = 0;
    for (int personOne = 0; personOne < personCount; personOne++) {
      for (int personTwo = personOne + 1;
           personTwo < personCount;
           personTwo++) {
        int pc = pairCount[personOne][personTwo];
        conflictCount += pc * (pc - 1) / 2;
      }
    }
    return conflictCount;
  }

  public static void main(String[] args) {
    Schedule sched = new Schedule(14, 11, 23);
    java.util.Random rand = new java.util.Random();
    int oldCc = sched.getConflictCount();
    while (oldCc > 0) {
      int week = rand.nextInt(sched.getWeekCount());
      int slotOne = rand.nextInt(sched.getPersonCount());
      int slotTwo = rand.nextInt(sched.getPersonCount());
      sched.swapWeekSlotPerson(week, slotOne, slotTwo);
      int newCc = sched.getConflictCount();
      if (newCc < oldCc) {
        oldCc = newCc;
      } else {
        sched.swapWeekSlotPerson(week, slotOne, slotTwo);
      }
    }
    for (int week = 0; week < sched.getWeekCount(); week++) {
      for (int group = 0; group < sched.getGroupCount(); group++) {
        for (int slot = sched.getGroupFirstSlot(group);
             slot < sched.getGroupFirstSlot(group + 1);
             slot++) {
          System.out.printf("%3d",
                            sched.getWeekSlotPerson(week, slot));
        }
        System.out.print('|');
      }
      System.out.println();
    }
  }
}


 类似资料:
  • 我正在尝试提出一种算法,用于将团队排序并分配给固定数量的用户。我发现的大多数算法都假设要除以的组数;我想创建一个智能系统,其中组自动分配(尽其最大能力),并根据总用户数以及每个组的最小和最大用户数进行预测。 为每一组假设以下标准: < li >每组最少3个 < li >每组最多6个 < li >基于用户总数的智能分组 以下是基于总用户数和每个组的最小/最大值的一些可能性: 对于24名成员: 4组5

  • 该问题给出了两个输入:数组(arr)和由数组构成子数组的次数(n)。子数组的和应该是奇数 已经很清楚,如果所有的数字都是偶数。奇数和子数组是不可能的。对于奇数和,连续的2个数字应该是奇数+偶数或者偶数+奇数。但我似乎不能把它们分成N个子数组。请帮忙解释一下逻辑。

  • 问题内容: 给定一周的工作量,我需要计算有多少人在工作。 这是我的人员表(日期为美国格式): 我希望在给定的一年中,所有星期数都与在此期间工作的适当人数保持一致。 希望您能理解我,因为英语不是我的母语。 我已经进行了一些研究,根据我的理解,根据以上示例,我需要创建一张表,从2006年1月1日开始,到“现在”结束(因为没有退出日期的人仍在工作)。能够测试每个人是否在本周内在工作,因此我可以在查询中算

  • 我得到了一个算法,可以用一种特定的方式写出欠费的顺序。 找到数组的最低数 将其保存在新数组的开头。 标记在我们找到最低数字的起源(起始)数组点(例如将其标记为最大int数字)。 回到第1点。 重复all以按升序重写所有数字。 所以我得到了一个可以改变顺序的工作代码,但我不知道如何标记数字,多亏了这一点,我创建了一个新的数组。

  • 问题内容: 给定一个整数数组,您需要将数组中的奇数和偶数分开。 请注意:元素的顺序可以更改。 例如: 问题答案: 让我们说数组是 初始化两个索引变量, 和 增加左变量直到你得到奇数 递减右边的变量,直到你得到偶数。 如果 ,交换 和 最后,您会看到左侧有偶数,右侧有奇数。 用于分隔数组中奇数和偶数的 Java 代码: 当你运行上面的程序时,你会得到以下输出:

  • 问题内容: 我有这个数组: 我想根据索引是偶数还是奇数将其分为两个数组,如下所示: 提前致谢! 问题答案: 一种解决方案,使用匿名函数和: 这样就可以将数组中的项一次分离出来,但是有点“聪明”。确实没有比经典的,更冗长的更好