下面是我要解决的问题的实质。我们有工作人员照顾孩子的托儿所设定的时间在周末。有16个不同的插槽，以填补一个周末。因此，对于一个4周月有64时隙来填补。我们以最大30苗圃工人（虽然我们需要更多。有人喜欢孩子吗？）。

Here's the essence of the problem I want to solve. We have workers taking care of children in a nursery for set times during the weekend. There's 16 different slots to fill in one weekend. So for a 4-week month there's 64 slots to fill. We have at max 30 nursery workers (though we need much more. anybody like kids?).

编辑：每个时隙是离散的 - 它们不重叠

Each time slot is discrete - they don't overlap.

目前有一个人每个月谁想出了幼儿园的时间表。这是一个复杂和耗时的任务，每月做这个时间表与每个人的preferences。在考虑这个问题我心想，必须有一个更好的办法！

Currently there's a person who comes up with the nursery schedule each month. It's a complex and time consuming task to make this schedule every month with everybody's preferences. After considering the problem I thought to myself, "There must be a better way!"

我注意到，这个问题本质上是一个二部图。该婚姻问题也是一个二分图，您可以用匹配算法求解如埃德蒙兹的匹配算法。

I notice that the problem is essentially a bipartite graph. The marriage problem is also a bipartite graph which you can solve by using a matching algorithm like Edmonds's matching algorithm.

但这种假设在一个节点集中的每个节点中的其他节点集中只有一个节点匹配。在我的情况下，每个苗圃工人将工作只有一个时隙。当我们正在严重不足，这是行不通的！一堆人都将不得不每月两次工作，以填补了所有的时间段。

But this assumes that each node in one node set matches just one node in the other node set. In my case, each nursery worker would work only one time slot. As we're seriously understaffed, that won't work! A bunch of people are going to have to work twice a month to fill up all the time slots.

这似乎意味着，这更像是经典的医院/居民的问题。它不同于婚姻问题，即女人可以接受来自一个以上的人，建议书（例如，医院可以采取多个居民）。就我而言，苗圃工人可以采取多个时隙。

Which seems to mean that this is more like the classic "hospitals/residents problem". It differs from the marriage problem in that the "women" can accept "proposals" from more than one "man" (e.g., a hospital can take multiple residents). In my case, a nursery worker can take more than one time slot.

呼！

现在，我已经设定了出路....没有任何一个知道的任何良好的联系，解释或显示这样的算法？有没有更好的方法去解决呢？上午我在想呢？我做了谷歌搜索住院医生算法，发现研究生的论文。尔加！我毕业于一个CS程度和采取了AI类...那是6年前。 帮助！的

Now that I have the set up out of the way....does any one know of any good links that explain or show such an algorithm? Are there better ways to go about solving this? Am I over thinking it? I did a google search for "hospital residents algorithms" and found grad student papers. Gah! I graduated with a CS degree and took an AI class...but that was 6 years ago. Help!

Aaaaany的建议是AP preciated !!

Aaaaany advice is appreciated!!

推荐答案

在医院/居民的问题确实可以工作，但它取决于你的约束：

The "hospitals/residents problem" could indeed work but it depends of your constraints :

在医院有一个最大容量，并下令居民（最想少想）。 居民将责令医院。 在没有其他方面的限制可能的。

在你的情况下，医院工作人员和居民的插槽。

In your case the hospitals are workers and the residents are slots.

在插槽可以订购工人（也许你$早晨p $ PFER试验的...）。 在工人可以为了插槽。 但你不能有其他限制，如：我早上的工作，我不想当天晚上上班

如果这是确定适合你，那么你必须可能性：

If that's ok for you then you have to possibilities :

要优势工人：医院为本案

you want to advantage workers : "hospital oriented case".

您将尝试工人分配给他们的preferred插槽（S）。

You will try to assign workers to their preferred slot(s).

要优势槽：居民为本案

每个插槽都会有自己的preferred工人。

Each slot will have their preferred workers.

我不得不code就在去年，这里是code。

I had to code it last year, here is the code.

/* 
RO : needed for Resident-Oriented version
HO : needed for Hospital-Oriented version
*/
const int MAX_R = 1000;
const int MAX_H = 1000;
const int INF = 1000*1000*1000;

您需要填写输入变量。 一切都非常简单：

You need to fill the input variables. Everything is straightforward :

R_ preF和H_ preF是preferences居民/医院列表 H_rank [H] [R]是R的H_ preF [H]等级：R的h的preference列表的位置

这就是全部。

// Input data
int R, H;                   // Number of Residents/Hospitals
int C[MAX_H];               // Capacity of hospitals
vector<int> R_pref[MAX_R], H_pref[MAX_H]; // Preferences : adjency lists
/*RO*/int H_rank[MAX_H][MAX_R];   // Rank : rank of r in H_pref[h]
/*HO*/int R_rank[MAX_R][MAX_H];   // Rank : rank of h in R_pref[r]

没有必要去碰以下。

// Internal data
int RankWorst[MAX_H];   // Rank of the worst r taken by h
/*RO*/int BestH[MAX_R];       // Indice of the best h in R_pref the r can get
/*HO*/int BestR[MAX_H];       // Indice of the best r in H_pref the h can get
int Size[MAX_H];        // Number of residents taken by h

// Output data
int M[MAX_R];

void stable_hospitals_RO()
{
    for(int h = 0 ; h < H ; h++)
      RankWorst[h] = H_pref[h].size()-1;
    fill_n(BestH, R, 0);
    fill_n(Size, H,0);
    fill_n(M,R,INF);
    for (int i = 0; i < R; i++)
        for (int r = i; r >= 0;)
        {
        if(BestH[r] == int(R_pref[r].size()))
            break;
            const int h = R_pref[r][BestH[r]++];
            if(Size[h]++ < C[h])
            {
                M[r] = h;
                break;
            }
            int WorstR = H_pref[h][RankWorst[h]];
            while(WorstR == INF || M[WorstR] != h) // Compute the worst
                WorstR = H_pref[h][--RankWorst[h]];
            if(H_rank[h][r] < RankWorst[h])        // Ranked better that worst
            {
                M[r] = h;
                M[r = WorstR] = INF;    // We have eliminate it, he need to put it somewhere
            }
        }
}
void stable_hospitals_HO()
{
    fill_n(BestR, H, 0);
    fill_n(Size, H,0);
    fill_n(M,R,INF);
    vector<int> SH;
    for (int h = 0; h < H; h++)
        SH.push_back(h);
    while(!SH.empty())
    {
        int h = SH.back();
        if(Size[h] == C[h] || BestR[h] == int(H_pref[h].size())) // Full or no r available
        {
            SH.pop_back();
            break;
        }
    const int r = H_pref[h][BestR[h]++];
    // r is unassigned or prefer h to current hospital
        if(M[r] == INF || R_rank[r][h] < R_rank[r][M[r]]) 
        {
            if(++Size[h] == C[h]) // Will be full
                SH.pop_back();
            if(M[r] != INF) // Delete from M[r]
            {
                Size[M[r]]--;
                SH.push_back(M[r]);
            }
            M[r] = h;
        }
    }
}

使用示例来说明如何构建preFS排名。 （在这种情况下，preference名单分别对标准输入）。

Example of use to show how to build rank from prefs. (In that case the preference lists were on the stdin).

int main()
{
    scanf("%d%d",&R,&H);
    int num;
    // put inf

    for(int r = 0 ; r < R ; r++)
    {
        scanf("%d",&num);
        R_pref[r].resize(num);
        for(int h = 0 ; h < num ; h++)
        {
            scanf("%d",&R_pref[r][h]);
            R_rank[r][R_pref[r][h]] = h;
        }
    }
    for(int h = 0 ; h < H ; h++)
    {
        scanf("%d",&C[h]);
        scanf("%d",&num);
        H_pref[h].resize(num);
        for(int r = 0 ; r < num ; r++)
        {
            scanf("%d",&H_pref[h][r]);
            H_rank[h][H_pref[h][r]] = r;
        }
    } 
    stable_hospitals_RO();
    printf("\n\n\n\n");
    stable_hospitals_HO();
    return 0;
}

在一个例子： 医院1至3个，6个居民

On an example : Hospitals 1 to 3, 6 résidents.

H_ preF：

1 - > 2 5 6 1（prefers 2然后5，然后6，然后1） 2 - > 4 2 1 6 3 5 3 - > 1 2

R_ preF：

1 - > 1 2 3 2 - > 3 1 3 - > 2 1 4 - > 1 3 2 5 - > 3 2 1 6 - > 3

H_rank：

1 - > 4 1的INF INF 2 3（1处于位置4中H_ $ P $粉煤[1]，3不是三项方） 2 - > 3 2 5 1 6 4 3 - > 1 2 INF INF INF INF

相似R_rank。

医院不必排名每个人等还可以排名少的人比​​他们的能力。

Hospital don't have to rank everyone et can also rank less people than their capacity.