Algorithme permettant de trouver la sum maximale d’éléments dans un tableau de sorte que pas plus de k éléments ne soient adjacents

Je suis tombé sur cette question. Dans un tableau contenant uniquement des valeurs positives, vous souhaitez maximiser la sum des éléments choisis sous la contrainte qu’aucun groupe de plus de k éléments choisis ne soit adjacent. Par exemple, si l’entrée est 1 2 3 1 7 9 (n = 6 et k = 2). La sortie sera 21, ce qui provient du choix des éléments _ 2 3 _ 7 9. Ma solution de DP simple est la suivante:

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

Mais je ne suis pas sûr que ce soit la solution efficace. La complexité peut-elle être réduite davantage? Merci de votre aide

Votre code est correct (du moins, la pensée est correcte), aussi, jusqu’à présent, je n’ai trouvé aucune donnée de test erronée. Suivez votre pensée, nous pouvons lister l’équation DP

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

Dans cette équation, P (v) signifie le maximum dans {C [v] ~ C [n]} (on laisse {C [1] ~ C [n]} la liste complète), il suffit donc de déterminer P (1).

Je n'ai pas trouvé de meilleure solution jusqu'à présent, mais votre code peut être optimisé. Après avoir déterminé P (v), vous pouvez enregistrer les données i. Ainsi, lorsque vous trouvez P (v-1), vous pouvez simplement comparer sum ( C [v-1] + C [v] ~ C [v + i-1]) + P [v + i + 1] avec P [v + 1] + C [v] lorsque i! = K, le pire la complexité est la même, mais la meilleure complexité est linéaire.

Je pense que ça va marcher:

 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 }