0

数日間、動的プログラミングの問題に苦しんでいます。次のようになります。ジョンの勤務日は N タイム スロットに分割されます。すべてのスロット i は、彼が受け取ることができるゲイン G[i] に関連付けられており、ジョンはそのタイム スロットで働いています。彼が時間間隔 [i, j] で作業することを決定した場合、最初のスロットはウォームアップのためであるため、彼の総報酬は R[i,j]=G[i+1]+...+G[j] になります。毎日、彼は正確に T スロットを働かなければなりません - 彼は利用可能な合計 N スロットから T スロットのサブセットを選ぶことができます。彼は、1 <= a1 <= b1 < a2 <= b2 <... の一連の選言間隔 [a1,b1]、[a2,b2]、...[ak,bk] を選択することによって、利益を最大化したいと考えています。 < ak <= bk および Sum[i=1, k](bi-ai+1)=T.

例: N=7、T=5、ゲイン ベクトル {3,9,1,1,7,5,4}。最適な解は、区間 [1,2] と [4,6] を選択して、総利益が 9+12=21 になるようにすることです。

4

1 に答える 1

0

DP ソリューション: int f[i][j][0..1];

let f[i][j][0] denotes the maximal gain for the first i time slots and using j time slots, and the i-th time slot is not used.
let f[i][j][1] denotes the maximal gain for the first i time slots and using j time slots, and the i-th time slot is used.

obviously,f[i][j][k] can determine f[i+1][j][k] or f[i+1][j+1][k]. details below:
f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0],f[i][j][1]+G[i+1]);
f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0],f[i][j][1]);
于 2013-03-12T06:18:16.603 に答える