2

私は現在、次の問題に取り組んでいます。

M個の正の数の配列が与えられた場合、特定の長さの連続した数のN個のブロックを取得する必要があります。たとえば、配列がある場合：

6 9 3 2 8 1 6 9 7

長さ3の1つのブロックを見つける必要がある場合、解は[3,2,8]であり、合計は13になります。2つのブロックを見つける必要がある場合、アルゴリズムは[3,2,8]と[1,6,9]これらのブロックのすべての要素の合計は最小であるため（29）。シーケンスの長さは常にブロックの長さのN倍よりも厳密に大きいことが与えられます（したがって、常に解決策があります）。

この問題はDPを使用することで解決できると思いますが、現在のところわかりません。サブ問題間の漸化式を見つけるのに苦労しています。誰かが私にここで手を貸してくれませんか？

前もって感謝します！

4

1 に答える 1

6

  1. 指定された長さの各ブロックの合計を計算し、それらを初期インデックスで記録します。これは、の複雑さによって行うことができますO(n)。したがって、次のようなリストが表示されます。

    index    sum
0        18
1        14
2        13
...      ...

  2. 目的のブロックが互いにオーバーラップすることができなかったため、それらのインデックスの各差は、指定された長さより小さくすることはできません。したがって、取得したリストに単純な動的計画アルゴリズムを適用する必要があります。

    ブロックの長さがl、リストnの長さが（たとえばリスト）で、ブロックS[n]を検索する場合は、m

    F(n,m,l) = min { F(n-i-l,m-1,l) + S[n-i] } (for i = 0 ~ n-(m-1)*l)

このステップの複雑さは、O(nm)必要mなブロック数です。

最後に、複雑さはO(nm)です。詳細が必要な場合はお知らせください。

于 2012-12-16T19:43:45.953 に答える