解決すべき問題があり、最適な解決策が見当たりません:/ 問題は次のとおりです。
n人の労働者とk人の仕事があります。各仕事は指定された数の労働者によって行われ、各労働者にはそれぞれの仕事の幸福度があります。労働者ができるだけ幸せになるように、仕事のスケジュールを立てなければなりません。したがって、int [n、k] (k >= n) の配列 a1 があります。i 番目の行の k 番目の列には、k 番目のジョブに対する i 番目のワーカーの優先度 (0 から 10 までの数字) が含まれます。また、int[k] の配列 a2 もあります。ここで、i 番目の要素には、その仕事をする人の数が含まれています。各労働者は同じ数の仕事をすることになっています。n >= max(a2) であることを知っているので、幸福の可能な最大の合計を見つけなければなりません。私の解決策は、再帰を使用することです。ジョブの最初の組み合わせの最初のワーカーを選択し、合計に設定を追加し、合計が既に見つかった最大値よりも大きいかどうかを確認し、大きい場合は次のワーカーに進みます。戻ったら、最初のワーカーなどの次の組み合わせを確認します。これは、少量のワーカーには問題なく機能しますが、より大きな問題を解決するには計算の複雑さが高くなります。より良い解決策のアイデアはありますか?
PS。別のサイトのガイがハンガリー語アルゴリズムの使用を勧めてくれましたが、n == k であると想定されており、n <= k で動作させる方法がわかりません。
PS2 例:
a1:
job1 job2 job3 job4
wokrer1 1 3 4 2
worker2 9 8 1 2
worker3 6 7 8 9
a2:
job1 job2 job3 job4
count 1 2 2 1
example solution:
worker1: job2, job3 (7)
worker2: job1, job2 (17)
worker3: job3, job4 (17)
sum: 41