Algoritmo para encontrar la suma máxima de elementos en una matriz tal que no más de k elementos son adyacentes

Question

Me encontré con esta pregunta. Dado un conjunto que contiene solo valores positivos, desea maximizar la suma de elementos elegidos bajo la restricción de que ningún grupo de más de k elementos elegidos es adyacente. Por ejemplo, si la entrada es 1 2 3 1 7 9 (n = 6 yk = 2). La salida será el 21, que trata de recoger los elementos _ _ 2 3 7 9. Mi solución simple DP es este

#include<stdio.h> 
#include<limits.h> 
#include<malloc.h> 


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>=n-k;i--){ 
     add += sums[i]; 
     maxsums[i] = add; 
    } 

    for(i = n-k-1;i>=0;i--){ 
     int j; 
     long sum =0,max = 0,cur; 
     for(j=0;j<=k;j++){ 
      cur = sum; 
      if((i+j+1)<n) 
       cur += maxsums[i+j+1]; 
      if(cur > 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)); 
} 

pero no estoy seguro de si esta es la solución eficiente. ¿Se puede reducir aún más la complejidad? Gracias por su ayuda

Answer 1

creo que esto va a funcionar:

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 
} 

Answer 2

Su código es correcto (al menos la idea es correcta), también, hasta ahora, no he encontrado ninguna prueba de datos erróneos. Siga su pensamiento, podemos enumerar la ecuación DP

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

En esta ecuación, P (v) significa el máximo en {C [v] ~ C [n]} (dejamos {C [1] ~ C [n]} ser la lista completa), así que solo necesitamos determinar P (1).

No he encontrado una solución mejor hasta ahora, pero su código se puede optimizar, después de determinar P (v), puede guardar los datos i, de modo que cuando encuentre P (v-1), puede simplemente compare la suma (C [v-1] + C [v] ~ C [v + i-1]) + P [v + i + 1] con P [v + 1] + C [v] cuando i! = k, la peor complejidad es la misma, pero la mejor complejidad es lineal.