6

私は次のような問題の解決策を考え出そうとしています。

  • Mをn行T列の行列とします。
  • 各行に正の非減少値を持たせます。（例：行= [1、2、30、30、35]）
  • M [i] [j]を、試験iにj単位の時間を費やして得られたスコアに対応させます。

動的計画法を使用して、問題を解決し、T単位の時間を学習に費やして、合計スコアが最も高くなる最適な方法を見つけます。

助けてくれてありがとう:)

私の試み：

S[][] = 0

for i = 1:n
   for j = 0:T
       max = 0
       for k = 0:j
           Grade = G[i][j]+ S[i-1][T-k]
           if Grade > max
              max = Grade
       end for
       S[i][j] = max
    end for
end for
4

2 に答える 2

10

最初の試験に費やす時間の単位をS[i][j]達成できる最高のスコアを表しましょう。の各値を調べることで計算できます。の各要素について、最良の結果が得られた前の行のの値を覚えておいてください。すべての試験を時間内に勉強するための最高のスコアは、まさにその答えです。覚えている値を使用して、各試験に費やす時間を決定できます。jiS[i][j]S[i-1][k]kSkTS[n][T]k

S[][] = 0

for j = 0:T
   S[0][j] = M[0][j]

for i = 1:n
   for j = 0:T
       max = 0
       for k = 0:j
           # This is the score you could get by spending j time, spending
           # k time on this exam and j-k time on the previous exams.
           Grade = S[i-1][j-k] + M[i][k]
           if Grade > max
              max = Grade
       end for
       S[i][j] = max
    end for
end for
于 2012-11-23T20:43:24.470 に答える
2

私はあなたの問題のvyGとMはあなたが同じことを意味していると思います、そしてあなたが試験に全く時間を費やさなければあなたは0のスコアを得ると思います。

この場合、DPマトリックスをD [i、t] =0からiまでの試験のサブセットに合計t単位の時間を費やすことによって達成可能な最高のスコアとして定義します。

Wlogでは、行列の最初の列をすべて0と見なすことができます。

この場合、Dが次の漸化式を満たすことがわかります。

  • D [0、t] = M [0、t]
  • D [i、t] = max_ {0 <= k <= t}（M [i、k] + D [i-1、tk]）

これは、動的計画法を適用するために必要なものです

于 2012-11-23T20:58:55.760 に答える