关于C#：在N个元素的数组中找到//’P//’个元素的最小总和，使得不超过//’k//’个连续元素一起被选中

Find the minimum sum of ‘P’ elements in an array of N elements such that no more than ‘k’ consecutive elements are selected together

假设数组是1 2 3 4 5
这里 N = 5 我们必须选择 3 个元素，我们不能选择超过 2 个连续的元素，所以 P = 3 和 k = 2。所以这里的输出将是 1 + 2 + 4 = 7.

我想出了一个递归解决方案，但它的时间复杂度是指数级的。这是代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#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 算法(如果存在)，或者更快的算法。

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

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

它基本上是这样工作的：

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

最初感觉这个问题只需要二维，但是，当我试图弄清楚时，我意识到我需要第三个。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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)

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/268950.html

关于C#：在N个元素的数组中找到//’P//’个元素的最小总和，使得不超过//’k//’个连续元素一起被选中

Find the minimum sum of ‘P’ elements in an array of N elements such that no more than ‘k’ consecutive elements are selected together

相关推荐

发表回复