収集できるリンゴの最大数

Question

最初は家の僧侶が1つの農場から別の農場まで順番に移動します。合計N個の農場があります。

ハウス - >第一farm->第二farm-> ... - > N番目の農場1つの農場から次のいずれかに実行

はモンクの現在のエネルギーの単一ユニットを消費します。 当初、モンクは彼の家にいて、最初の農場に移動するためには、彼にエネルギーの1単位が必要です。

あなたは配列ミルク[N]とりんご[N]と僧侶の初期エネルギー（家で）Pを与えられています。

各農場で、モンクは、（乳量：ミルク[i]の量でエネルギーを増やす）か、農場のリンゴを選ぶかのいずれかの選択肢があります。モンクは、ミルクの全量またはリンゴの全量のみを取ることができ、どちらかまたは両方を取ることはできません。

次のようにして、モンクが収集できるリンゴの最大数は何ですか、常に負ではないエネルギーがありますか？

例：

N = 3 
P = 2 
milk = {1, 2, 1} 
apples = {100, 1, 100} 

ans = 200 

どれアプローチまたは上記の質問を解決するためのアルゴリズム..

Answer 1

使用：次に

dp[i, j] = max{dp[i-1, j+1] + apples[i] # Take the apples at i, only if j >= 0 
       dp[i - 1, j - energy[i]] # Take the energy at i 

：

dp[i, j] = maximum amount of apples possible if we are at farm i 
      with j energy 

我々は再発を持っています0の最大値を取る（ゼロインデックスを使用している場合）ご例えば

、dpは次のようになります。

dp[0, P-1] = dp[0, 1] = apples[0] = 100 
dp[0, P-1+milk[0]] = dp[0, 2] = 0 
dp[0, anything else] = -inf 

dp[1, 0] = max{dp[0, 0 + 1] + apples[1], 
       dp[0, 0 - 2]} 
     = 101 
dp[1, 1] = max{dp[0, 1 + 1] + apples[1], 
       dp[0, 1 - 2]} 
     = max{0 + 1, -inf} 
     = 1 
dp[1, 2] = max{dp[0, 2 + 1] + apples[1], 
       dp[0, 2 - 2]} 
     = -inf 
dp[1, 3] = max{dp[0, 3 + 1] + apples[1], 
       dp[0, 3 - 2]} 
     = 100 

dp[2, 0] = max{dp[1, 0 + 1] + apples[2], 
       dp[1, 0 - 2]} 
     = 101 
dp[2, 1] = max{dp[1, 1 + 1] + apples[2], 
       dp[1, 1 - 2]} 
     = -inf 
dp[2, 2] = max{dp[1, 2 + 1] + apples[2], 
       dp[1, 2 - 2]} 
     = max{200, 101} 
     = 200 

あなたはmilk[0] + milk[1] + ... + milk[i]の合計までアップi番目の反復にjを反復処理する必要があります。

行列の代わりに1つまたは2つの配列を使用するなど、さまざまな最適化が可能です。