-1

私は課題を読んでいましたが、それは私には割り当ての問題のように見えました.ここに要約があります.会社にはN個の仕事があります.N人の候補者が応募しましたが、異なる時期に.

セル (i,j) が求職者 i が j 番目に会社に近づく時刻を表す NxN マトリックスが与えられます。有効な1 対 1 の割り当てを見つける必要があります。仕事が候補者に割り当てられた場合、その候補者はそれ以上の仕事を探しません.2人の候補者に同じ仕事を与えてはなりません.また、任意の時点で2人の候補者が同じ職場にいてはなりません.出力は、任意の順列である必要があります.上記の制約を満たします。

例: 入力:

1 2 3

4 5 6

7 8 9

出力：

3 2 1

説明: 時間 = 1 秒で 1 番目の候補は最初のジョブに移動し、次に時間 = 2 秒で 2 番目のジョブに移動します。したがって、彼は時間 = 6 でジョブ 3 に行くことはありません。最終的に、最初のジョブは t = 7 で 3 番目のジョブに割り当てられます。

他の順列は正しくないことに注意してください。出力 (1 2 3) の場合は、最初の候補が最初のジョブに割り当てられるため、正しくありません。したがって、彼はジョブ 2 と 3 を検索しません。しかし、4 秒で 2 番目の候補はまた、すでにオフィスに最初の人がいる最初の仕事にも応募してください。

私の質問は、そのような割り当ての問題にどのように対処するかということです??

4

2 に答える 2

0

(i, j) を時間で並べると、最後に応募した人にその仕事を与えます。早い時間に他のすべてのジョブに対応できる人がまだいます (そうでなければ、最大時間ではなかったからです)。これを繰り返し続けると、かなり早く割り当てが得られます。

matrix = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

dictionary = {}
for person in range(3):
    for job in range(3):
        time = matrix[person][job]
        dictionary[time] = (person, job)

ordered_time = sorted(dictionary.keys(), reverse=True)

taken_job = set()
taken_person = set()
assignment = []
for time in ordered_time:
    person, job = dictionary[time]
    if person not in taken_person and job not in taken_job:
        assignment.append("t=%s, i=%s, j=%s" % (time, person, job))
        taken_job.add(job)
        taken_person.add(person)

print(assignment)
#['t=9, i=2, j=2', 't=5, i=1, j=1', 't=1, i=0, j=0']
于 2012-08-05T22:37:09.433 に答える
0

これは、現在開催中の CodeChef August Challenge プログラミング コンテストの BLOCKING 問題です。競技中にこの種のヒントを求めることはルール違反です。

http://www.codechef.com/AUG12/problems/BLOCKING

週末に競技会が終了すると、他の競技者の回答を見て自分の回答を得ることができます。

于 2012-08-07T23:54:29.003 に答える