要するに、私の問題は、整数配列でいくつかの整数「パターン」を見つけることです。結果は、抽出されたすべてのパターンの合計値に関して最適である必要があります。
具体的には、配列とパターンの要素は負でない整数です。この配列のいくつかの連続した要素 (パターンと同じ長さ) からパターンを差し引いたときに、配列内のすべての要素が非負のままである場合、配列からパターンを抽出できると言います。
要素は整数であるため、文字列パターンとは異なり、すべてのパターンを複数回抽出できます。たとえば、配列 = {1, 2, 1} とパターン = {1, 1} が与えられた場合、配列内にそのようなパターンが 2 つ見つかります。最初のパターンは、配列 {1, 2 の最初の 2 つの項目に含まれています。 2}、配列から 1 つのパターンを抽出した後、配列は {0, 1, 1} になり、配列の最後の 2 つの項目から 2 番目の {1, 1} パターンを抽出できます。
すべてのパターンには価値があります。パターンが i 回抽出されると、値も i 倍されます。目標は、最終的に合計値を最大化する一連のパターン抽出を見つけることです。
貪欲なアルゴリズムを使用しようとしました。つまり、最初に最大単位値を持つパターンを抽出しようとしましたが、まだ問題があります。配列に複数の最大値パターンがある場合、どれを最初に選択するか? ここで使われている貪欲な戦略は、ナップザック問題を思い起こさせますが、それらは異なります。さらに、貪欲なアルゴリズムの最適性は疑わしいものです。動的計画法のアルゴリズムを考えていましたが、今は完全に空白です。
問題が明確になったことを願っています。助言がありますか？