python - 最大化一系列值的组合

Question

这是一个复杂的问题，但我怀疑我可以应用一些原则来使它变得简单——我只是不知道它是什么。

我需要为本学期的全类学生分配演示时段。有多个可能的日期和多种演示类型。我进行了一项调查，学生可以对他们对不同主题的兴趣进行排名。我想做的是为学生分配最好的(或至少是好的)演示时段。

所以，我有:

• 12 个日期列表
• 18 名学生名单
• CSV 文件，每个学生(行)在每个日期的评分为 1-5

我想得到的:

• 每个学生应该有一种演示类型 A(介绍)，一种演示类型 B(图形)和 3 种演示类型 C(目标)
• 每个日期应至少有每种类型的演示
• 每个日期不应超过 2 个类型 A 或类型 B
• 尝试向学生展示他们评价很高(4 或 5)的演讲

我应该指出，我意识到这看起来像是一道家庭作业题，但这是现实生活:-)。我想我可以为每个学生创建一个 Student 类，其中包含每种演示类型的日期，但我不确定填充它的最佳方法是什么。实际上，我什至不确定从哪里开始。

Answer 1

TL;DR:我认为您给了学生太多选择 :D

但无论如何我都有机会解决这个问题。实际上非常有趣的练习，尽管有些限制有点模糊。最重要的是，我不得不猜测实际学生的偏好分布是什么样的。我选择了均匀分布的独立变量，尽管这可能不太现实。我仍然认为它在真实数据上的效果应该和在随机生成的数据上一样好。

我考虑过暴力破解，但粗略的分析让我估计有超过 10^65 种可能的配置。那是很多。由于我们没有万亿年的时间来考虑所有这些问题，因此我们需要一种启发式方法。

由于问题的规模，我尽量避免进行任何回溯。但这意味着您可能会陷入困境；可能没有解决方案，每个人都只得到他们给 4 和 5 的日期。

我最终实现了双刃剑 Iterative Deepening -类似于搜索，我们仍然对最好情况抱有希望(即，将学生分配到他们给出 5 分的日期)和最坏情况愿意接受(有些学生可能不得不接受 3)逐渐降低，直到找到解决方案。如果我们卡住了，重新设定，降低期望，然后再试一次。先分配任务A和B，A和B完成后才完成C，因为C的约束远没有那么严格。

我还使用了一个权重因子来模拟最大限度地提高学生的幸福感与满足每天的演示类型限制之间的权衡。

目前，它似乎可以为几乎所有随机生成的首选项集找到解决方案。我包括了一个评估指标；所有指定学生/日期组合的偏好值总和与所有学生理想/前 3 名偏好值总和之间的比率。例如，如果学生 X 在他的列表中有两个 5、一个 4 和其余的 3，并且分配给他的 1 个 5 和 2 个 3，他得到 5+3+3=11，但理想情况下本可以得到 5+5+ 4=14；他的满意度为 11/14 = 78.6%。

经过一些测试，我的实现似乎倾向于产生大约 95% 的平均学生满意度，比我预期的要好很多 :) 但同样，这是使用假数据。真正的偏好可能更集中，更难满足。

下面是算法的核心。完整的脚本大约有 250 行，我认为这里有点太长了。看看at Github .

...

# Assign a date for a given task to each student, 
# preferring a date that they like and is still free.
def fill(task, lowest_acceptable, spread_weight=0.1, tasks_to_spread="ABC"):
        random_order = range(nStudents) # randomize student order, so everyone
        random.shuffle(random_order)    # has an equal chance to get their first pick
        for i in random_order:
            student = students[i]
            if student.dates[task]: # student is already assigned for this task?
                continue

            # get available dates ordered by preference and how fully booked they are
            preferred = get_favorite_day(student, lowest_acceptable,  
                                         spread_weight, tasks_to_spread)
            for date_nr in preferred:
                date = dates[date_nr]
                if date.is_available(task, student.count, lowest_acceptable == 1):
                    date.set_student(task, student.count)
                    student.dates[task] = date
                    break

# attempt to "fill()" the schedule while gradually lowering expectations
start_at = 5
while start_at > 1:
    lowest_acceptable = start_at
    while lowest_acceptable > 0:
        fill("A", lowest_acceptable, spread_weight, "AAB")
        fill("B", lowest_acceptable, spread_weight, "ABB")
        if lowest_acceptable == 1:
            fill("C", lowest_acceptable, spread_weight_C, "C")
        lowest_acceptable -= 1

这是脚本打印的示例结果:

                                      Date                                      
================================================================================
Student |  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  10 |  11 |  12 |
================================================================================
   1    |     |  A  |  B  |     |  C  |     |     |     |     |     |     |     |
   2    |     |     |     |     |  A  |     |     |     |     |  B  |  C  |     |
   3    |     |     |     |     |  B  |     |     |  C  |     |  A  |     |     |
   4    |     |     |     |  A  |     |  C  |     |     |     |     |     |  B  |
   5    |     |     |  C  |     |     |     |  A  |  B  |     |     |     |     |
   6    |     |  C  |     |     |     |     |     |     |  A  |  B  |     |     |
   7    |     |     |  C  |     |     |     |     |  B  |     |     |     |  A  |
   8    |     |     |  A  |     |  C  |     |  B  |     |     |     |     |     |
   9    |  C  |     |     |     |     |     |     |     |  A  |     |     |  B  |
   10   |  A  |  B  |     |     |     |     |     |     |  C  |     |     |     |
   11   |  B  |     |     |  A  |     |  C  |     |     |     |     |     |     |
   12   |     |     |     |     |     |  A  |  C  |     |     |     |  B  |     |
   13   |  A  |     |     |  B  |     |     |     |     |     |     |     |  C  |
   14   |     |     |     |     |  B  |     |     |     |  C  |     |  A  |     |
   15   |     |     |  A  |  C  |     |  B  |     |     |     |     |     |     |
   16   |     |     |     |     |     |  A  |     |     |     |  C  |  B  |     |
   17   |     |  A  |     |  C  |     |     |  B  |     |     |     |     |     |
   18   |     |     |     |     |     |     |  C  |  A  |  B  |     |     |     |
================================================================================
Total student satisfaction: 250/261 = 95.00%