私はいくつかの質問をしていましたが、ここで質問を見つけました。動的計画法アルゴリズムが必要です。再発を考え出そうとしましたが、常に正しい結果が得られるとは思いません。制限 K を考慮しないと、最小時間を見つける再発が起こりやすくなります。これは、貪欲なアプローチを使用しても実行できると思います。間違っている場合は修正してください。ただし、制限 K については、後の段階でマシン A の値 i を使用することを考えるかもしれませんが、それは K 制限を完了している可能性があることを考慮する必要があります。したがって、これは後戻りする必要があります。これを考慮に入れるには、もう 1 つの次元を維持する必要があるのではないかと思います。しかし、余剰次元を使って、その状況をどのように包み込むかを考えることができません。助けてください。
2 台のマシンが与えられます。あなたが実行しなければならない N 個の仕事があります。ジョブ i は、マシン A で実行するのに Ai 時間、マシン B で実行するのに Bi 時間かかります。各ジョブは、マシン A または B のいずれかで実行する必要があります。ジョブは順番に実行する必要があります。配列 A と B および整数 K が与えられた場合、同じマシンで K 個を超えるジョブを連続して実行できないことを前提として、ジョブを完了するのに必要な最小時間を見つけます。これは O(NK) 空間と時間で実行できます。これは、O(NK) 時間と O(N ) 空間、さらに O(N logN ) 時間に改善できます。