Algoritmo per trovare la somma massima di elementi in una matrice tale che non più di k elementi sono adiacenti

Question

Mi sono imbattuto in questa domanda. Dato un array contenente solo valori positivi, si desidera massimizzare la somma degli elementi scelti sotto il vincolo che nessun gruppo di più di k elementi scelti sono adiacenti. Ad esempio se l'input è 1 2 3 1 7 9 (n = 6 e k = 2). L'uscita sarà il 21, che proviene dalla raccolta degli elementi _ _ 2 3 7 9. La mia soluzione semplice DP è questo

#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)); 
} 

Ma io non sono sicuro se questa è la soluzione efficace. La complessità può essere ulteriormente ridotta? Grazie per il vostro aiuto

Answer 1

credo che questo funzionerà:

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

Il vostro codice è corretto (almeno il pensiero è corretto), anche, fino ad ora, non ho trovato alcun dato di test sbagliati. Segui il tuo pensiero, possiamo elencare l'equazione DP

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

In questa equazione, P (v), il quantitativo massimo di {C [v] ~ C [n]} (lasciamo {C [1] ~ C [n]} è l'intera lista), quindi abbiamo solo bisogno di determinare P (1).

Non ho trovato una soluzione migliore fino ad ora, ma il codice può essere ottimizzato, dopo aver determinato P (v), è possibile salvare i dati i, quindi quando si trova P (v-1), è possibile confronta solo la somma (C [v-1] + C [v] ~ C [v + i-1]) + P [v + i + 1] con P [v + 1] + C [v] quando i! = k, la peggiore complessità è la stessa, ma la migliore complessità è lineare.