問題は、n個の数字で満たされた配列があることです。合計の最大値を求めなければなりませんが、i の位置の数値を加算すると、i-1 と i+1 の数値は加算できません。
n の数は、循環にあると見なされます。
たとえば、次の配列がある場合:
{6, 9, 1, 2, 8, 6, 3, 7, 12, 5, 65, 66, 2} 最大合計は 99 です: 9 + 8 + 3 +12+ 65 + 2 = 99
2 に答える
1
配列の最初の要素が含まれていることがわかっているとします。次に、動的計画法でこれを解決できます。i = 3 から N - 1 の場合、要素 i を含めるか含めないかの選択を考慮し、以前に計算されたスコアを見て、配列の最初の i メンバーの最適解を見つけます。最初の i-1 または i-2 要素が i 要素に対してできる最善の解決策を見つけます。最初の要素を含めたために最後の要素を含めることができず、最初の 2 つの要素のスコアは最初の要素を含めたため、最初の要素のスコアと同じであるため、N 個の要素について最善を尽くす必要はありません。 .
もう 1 つの可能性は、最初の要素が含まれていないことです。ただし、i = 2 から N までの可能性を考慮することを除いて、同じ方法でこれに対する最高のスコアを計算できます。
これで、考えられる 2 つのケース (最初の要素が含まれているか含まれていないか) に対する答えが得られたので、最適な方を選択します。
PS - これが宿題でない場合、実際にこれの有用なアプリケーションはありますか? それは何ですか？
于 2012-12-06T05:27:54.933 に答える