7

N 個の仕事と、それらの仕事をする K 人の労働者が与えられたとしましょう。ただし、2 人の従業員が必要な仕事もあれば、1 人で済む仕事もあります。また、従業員はすべての仕事を行うことはできません。たとえば、労働者 1 は仕事 1、2、および 5 を実行できますが、仕事 3 および 4 は実行できません。また、仕事 1 を実行するために労働者 1 を雇う場合、すでに支払いを済ませているため、仕事 2 および 5 を実行してもらいます。

たとえば、5 つのジョブと 6 つのワーカーがあるとします。ジョブ 1、2、および 4 では 2 人の男性が必要ですが、ジョブ 3 および 5 では 1 人で十分です。そして、これがすべての労働者ができる仕事と彼が必要とする賃金のリストです.

Worker 1 can do jobs 1,3,5 and he requires 1000 dollars. 
Worker 2 can do jobs 1,5 and he requires 2000 dollars. 
Worker 3 can do jobs 1,2 and he requires 1500 dollars. 
Worker 4 can do jobs 2,4 and he requires 2500 dollars. 
Worker 5 can do jobs 4,5 and he requires 1500 dollars. 
Worker 6 can do jobs 3,5 and he requires 1000 dollars.

少しの計算と論理的思考の後で、労働者 1、3、4、5 を雇う必要があると結論付けることができます。つまり、支払う必要のある最低賃金は、1000 + 1500 + 2500 + 1500 = 5500 ドルです。

しかし、その量を出力する効率的なアルゴリズムをどのように見つけることができるのでしょうか? これはどういうわけかハンガリーのアルゴリズムを思い出させますが、これらの追加の制約により、私はそれを適用することができません.

4

1 に答える 1

2

すべての仕事の状態は、3 進法 (2 - 残り 2 人、1 - 残り 1 人、すでに完了している場合は 0) の数字として表すことができます。f(mask, k) = 残りのジョブの状態がマスクになるように、最初の k 人の中から何人かの労働者を雇うための最小コストを計算できます。遷移は次のとおりです: (mask, k + 1) (現在の労働者を雇わない) に行くか、(new_mask, k + 1) に行く (この場合、この労働者に給与を支払い、彼にすべての作業を任せます)彼ができる仕事）。答えは f(0, K) です。

時間計算量は O(3^N * K * N) です。

Nこれをさらに最適化する（そして要因を取り除く）方法のアイデアを次に示します。mask現在のマスクがであり、男性が別の からジョブを実行できると仮定しましょうmask'。実際には単純にに足すこともできますがmask、mask'1 つ問題があります。しかし、修正することができます: 各マスクについて、数字が ではないすべての位置を含むバイナリ マスクを事前計算しましょう。人それぞれについて、その値を事前に計算できます。各トランジションは 1 つの追加にすぎません。2mask1mask'allowed_mask2allowed_maskmask'

for i = 0 ... k - 1
    for mask = 0 ... 3^n - 1
        allowed_mask = precomputed_allowed_mask[mask]
        // make a transition to (i + 1, mask + add_for_allowed_mask[i][allowed_mask])
        // make a transition to (i + 1, mask)

2^n許可されているマスクしかないことに注意してください。したがって、このソリューションの時間の複雑さは次のとおりですO(3^N * N + T * 2^N * K * N + T * 3^N * K)(最初の項はすべての 3 値マスクの allowed_masks の事前計算、2 番目の項はmask'すべての allowed_masks と人の事前計算、最後は dp 自体の計算です)。

于 2015-04-09T23:49:12.140 に答える