c++ - 在 N 个元素的数组中找到 'P' 个元素的最小总和，使得不超过 'k' 个连续元素一起被选中

Question

假设数组是1 2 3 4 5这里 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 算法(如果存在的话)，或者更快的算法。

我已经尝试了各种测试用例并得到了正确的答案。如果您发现一些测试用例给出了错误的响应，也请指出。

Answer 1

下面是一个Java动态规划算法。
(C++版本看起来应该很相似)

它的基本工作原理如下:

• 有一个 3D 数组 [pos][consecutive length][length]
  这里length index = actual length - 1 ), 所以 [0]将是长度 1，对于连续长度也是如此。这样做是因为任何地方的长度都为 0 是没有意义的。
• 在每个位置:
  • 如果长度为 0 且连续长度为 0，则只使用 pos 处的值.
  • 否则，如果连续长度为 0，则使用 pos - 1 查找所有先前位置(length - 1 除外)中的最小值并使用它加上 pos 处的值.
  • 对于其他一切，如果pos > 0 && consecutive length > 0 && length > 0 ,
    使用 [pos-1][consecutive length-1][length-1]加上 pos 处的值.
    如果其中之一为 0，则将其初始化为无效值。

最初感觉这个问题只需要 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(N<sup>2</sup>k + NPk)