用于找到arrays中元素的最大总和以使得不多于k个元素相邻的算法

我遇到了这个问题。 给定一个仅包含正值的数组，您希望在约束条件下最大化所选元素的总和，使得多于k个选定元素的组不相邻。 例如，如果输入是1 2 3 1 7 9（n = 6且k = 2）。 输出将是21，它来自挑选元素_ 2 3 _ 7 9.我的简单DP解决方案就是这样

#include #include #include long maxsum(int n,int k,long *sums){ long *maxsums; maxsums = malloc(sizeof(long)*n); int i; long add = 0; for(i=n-1;i>=nk;i--){ add += sums[i]; maxsums[i] = add; } for(i = nk-1;i>=0;i--){ int j; long sum =0,max = 0,cur; for(j=0;j<=k;j++){ cur = sum; if((i+j+1) max) max = cur; sum += sums[i+j]; } maxsums[i] = max; } return maxsums[0]; } int main(){ int cases=0,casedone=0; int n,k; long *array; long maxsum = 0; fscanf(stdin,"%d %d",&n,&k); array = malloc(sizeof(long)*n); int i =0; while(casedone < n){ fscanf(stdin,"%ld",&array[casedone]); casedone++; } printf("%ld",maxsum(n,k,array)); } 

但我不确定这是否是有效的解决方案。 可以进一步降低复杂性吗？ 谢谢你的帮助

Answer 1

你的代码是正确的（至少思想是正确的），同样，到目前为止，我还没有发现任何错误的测试数据。 按照你的想法，我们可以列出DP方程

P(v)=max{sum(C[v]~C[v+i-1])+P(v+i+1),0<=i<=k}

在这个等式中，P（v）表示{C [v] ~C [n]}中的最大值（我们让{C [1] ~C [n]}成为整个列表），所以我们只需要确定P （1）。

到目前为止我还没有找到更好的解决方案，但是你的代码可以优化，在你确定P（v）后，你可以保存数据i，所以当你找到P（v-1）时，你可以只比较sum（ C [v-1] + C [v] ~C [v + i-1]）+ P [v + i + 1]与P [v + 1] + C [v]当i！= k时，最差复杂性是相同的，但最好的复杂性是线性的。

Answer 2

我认为这会奏效：

 findMaxSum(int a[], int in, int last, int k) { // in is current index, last is index of last chosen element if ( in == size of a[] ) return 0; dontChoseCurrent = findMaxSum(a, in+1, last, k); // If current element is negative, this will give better result if (last == in-1 and k > 0) { // last and in are adjacent, to chose this k must be greater than 0 choseCurrentAdjacent = findMaxSum(a, in+1, in, k-1) + a[in]; } if (last != in-1) { // last and in are not adjacent, you can chose this. choseCurrentNotAdjacent = findMaxSum(a, in+1, in, k) + a[in]; } return max of dontChoseCurrent, choseCurrentAdjacent, choseCurrentNotAdjacent }