2

配列が1 2 3 4 5 Here でN = 5あり、3 つの要素を選択する必要があり、2 つ以上の連続する要素を選択できないためP = 3、 とk = 2. したがって、ここでの出力は になります1 + 2 + 4 = 7。

再帰的な解決策を思いつきましたが、指数関数的な時間の複雑さがあります。これがコードです。

#include<iostream>

using namespace std;

void mincost_hoarding (int *arr, int max_size, int P, int k, int iter, int& min_val, int sum_sofar, int orig_k)
{
    if (P == 0)
    {
        if (sum_sofar < min_val)
            min_val = sum_sofar;
        return;
    }

    if (iter == max_size)
        return;



    if (k!=0)
    {
        mincost_hoarding (arr, max_size, P - 1, k - 1, iter + 1, min_val, sum_sofar + arr[iter], orig_k);
        mincost_hoarding (arr, max_size, P, orig_k, iter + 1, min_val, sum_sofar, orig_k);
    }
    else
    {
        mincost_hoarding (arr, max_size, P, orig_k, iter + 1, min_val, sum_sofar, orig_k);
    }

}



int main()
{
    int a[] = {10, 5, 13, 8, 2, 11, 6, 4};

    int N = sizeof(a)/sizeof(a[0]);
    int P = 2;
    int k = 1;


    int min_val = INT_MAX;
    mincost_hoarding (a, N, P, k, 0, min_val, 0, k);

    cout<<min_val;

}

また、制約に従って P 要素を選択できない場合は、INT_MAX を返します。

インタビューでこんな質問をされました。この解決策を提案した後、インタビュアーはもっと速いものを期待していました。おそらく、問題に対するDPアプローチです。DPアルゴリズムが存在する場合、またはより高速なアルゴリズムを提案できますか。

さまざまなテストケースを試しましたが、正しい答えが得られました。誤った応答を返すテスト ケースを見つけた場合は、それも指摘してください。

4

1 に答える 1

3

以下は、Java 動的プログラミング アルゴリズムです。
(C++ バージョンは非常に似ているはずです)

基本的には次のように機能します。

  • [pos][consecutive length][length]
    Here length index = actual length - 1)の 3D 配列を持っている[0]ため、連続した長さの場合と同様に、長さは 1 になります。これは、どこでも長さが 0 であっても意味がないためです。
  • すべての位置で:
    • 長さが 0 で連続長が 0 の場合は、 at の値をそのまま使用しますpos。
    • pos - 1それ以外の場合、連続する長さが 0 の場合は、前のすべての位置 ( を除く)の最小値を で探し、length - 1それに の値を加えた値を使用しますpos。
    • それ以外の場合pos > 0 && consecutive length > 0 && length > 0は、の値に加えてを
      使用します。 それらのいずれかが 0 の場合は、無効な値に初期化します。[pos-1][consecutive length-1][length-1]pos

最初は、この問題には 2 次元しか必要ないように感じましたが、理解しようとするとすぐに、3 次元が必要であることに気付きました。

コード：

  int[] arr = {1, 2, 3, 4, 5};
  int k = 2, P = 3;

  int[][][] A = new int[arr.length][P][k];

  for (int pos = 0; pos < arr.length; pos++)
  for (int len = 0; len < P; len++)
  {
     int min = 1000000;
     if (len > 0)
     {
        for (int pos2 = 0; pos2 < pos-1; pos2++)
        for (int con = 0; con < k; con++)
           min = Math.min(min, A[pos2][len-1][con]);
        A[pos][len][0] = min + arr[pos];
     }
     else
        A[pos][0][0] = arr[pos];

     for (int con = 1; con < k; con++)
        if (pos > 0 && len > 0)
           A[pos][len][con] = A[pos-1][len-1][con-1] + arr[pos];
        else
           A[pos][len][con] = 1000000;
  }

  // Determine the minimum sum
  int min = 100000;
  for (int pos = 0; pos < arr.length; pos++)
  for (int con = 0; con < k; con++)
     min = Math.min(A[pos][P-1][con], min);
  System.out.println(min);

ここでは7、予想どおり、出力として得られます。

実行時間： O(N2k + NPk)

于 2013-09-17T12:29:30.893 に答える