2

私はプログラミングコンテストサイトでこの問題に遭遇し、数日間さまざまなことを試しましたが、どれも十分に効率的ではないようです。

ここに質問があります：あなたは整数の大きな配列と数kを与えられます。目標は、すべてのサブ配列のすべての要素の合計が最大になるように、配列をそれぞれk個以下の要素を含むサブ配列に分割することです。もう1つの条件は、これらのサブアレイのいずれも互いに隣接できないことです。つまり、元の配列からいくつかの用語を削除する必要があります。

それはしばらくの間私を悩ませてきました、そしてこの問題に取り組むことについてのあなたの見解を聞きたいです。

4

3 に答える 3

3

動的計画法でうまくいくはずです。理由の簡単な説明：

動的計画法の影響を受けやすい問題の重要な特性は、問題の最適解（ここでは配列全体）を常にサブ問題の2つの最適解（ここでは2つのサブ配列）の合成として表現できることです。すべての分割が必要なわけではありません。このプロパティ-最適なソリューションを得るには、そのような分割が1つ存在するだけで十分です。

明らかに、（ドロップされた要素の）配列間で最適なソリューションを分割すると、サブソリューションは両方のサブアレイ内で最適になります。

アルゴリズム：

配列のすべての要素を分割要素として順番に試し、最良の結果が得られる要素を探します。配列の両方の部分について再帰的に問題を解決します（サブ配列がk）より長くならない場合、再帰は停止します。指数関数的な時間を避けるためにソリューションをメモ化します（再帰は明らかに同じサブアレイを何度も試行します）。

于 2012-04-24T15:22:47.033 に答える
0

これは解決策ではありませんが、手がかりです。

次の問題を解決することを検討してください。

配列Xから、要素のサブセットを選択して、それらのいずれも互いに隣接せず、それらの合計が最大になるようにします。

さて、上記の問題は、K=1の問題の特殊なケースです。ソリューションを一般的なケースに拡張する方法を考えてください。より単純なケースを解決する方法がわからない場合はお知らせください。

于 2012-04-24T17:05:36.170 に答える
0

なぜこれが機能するのかを説明する時間がなく、受け入れられる答えになるはずです：

def maxK(a, k): 
    states = k+1
    myList = [0 for i in range(states)]
    for i in range(0, len(a)): 
        maxV = max (myList)
        myList = [a[i] + j for j in myList]
        myList[(states-i) % k] = maxV  
    return max(myList)

これは負の数でも機能します。これはsize(a)時間的に線形kです。私が使用した言語はPythonです。このレベルでは、疑似コードであるかのように読み取ることができるためです。

于 2018-11-15T14:50:07.173 に答える