Trovare la sottosequenza più lunga con una somma inferiore o uguale a un numero fisso

Question

Trovare la sottosequenza più lunga con una somma inferiore o uguale a un numero fisso

#1 da (2 voti)
#2 da (1 voti)
#3 da (0 voti)

4

Stavo cercando di risolvere Problema 279-B .

Given an natural number, t, and an array, a[0],...,a[n-1], of natural numbers, find the maximum length of a continuous subarray, a[i],...,a[j] in a where a[i]+...+a[j] <= t. e.g. a=[3,1,2,1] and t=5 -> 3(1,2,1) ; a=[2,2,3] and t=3 -> 1
Ho pensato ad una soluzione O (n ²).

Double looping to calculate sums and kind of brute force.
Ho anche pensato alla somma massima di un sottoarray in un array mediante la programmazione dinamica.
Ho visto questa soluzione che è O (n lg n )

By creating a sum array defined as:

sum[i]=sum[i−1]+array[i]//  for  all   i>0.
sum[i]=array[i]    // for   i=0

Then finding j such that (by binary search)

sum[j]−sum[i]//j>i

Ho visto questa soluzione (1) che è simile a questa soluzione a un altro problema (2) che hanno entrambi la stessa soluzione O (n).

Soluzione 1:

    int n; long t; scanf("%d %ld", &n, &t);
    long *minutes = new long[n];
    long totalTime = 0;
    for(int k = 0; k < n; k++){scanf("%ld", minutes + k); totalTime += minutes[k];}

    long start(0), finish(0), currentSum(0), output(0);

    while(finish < n){
        currentSum += minutes[finish++];
        while(currentSum > t){currentSum -= minutes[start++];}
        if(output < finish - start){output = finish - start;}
    }

    printf("%ld\n", output);

    delete[] minutes;
    return 0;

Soluzione 2:

    int curr_sum = arr[0], start = 0, i;

    for (i = 1; i <= n; i++)
    {
    // If curr_sum exceeds the sum, then remove the starting elements
       while (curr_sum > sum && start < i-1)
       {
            curr_sum = curr_sum - arr[start];
            start++;
        }
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }
    printf("No subarray found");
    return 0;

Perché funziona l'ultimo approccio (Soluzione 1 per somma inferiore a un numero fisso e soluzione 2 per somma uguale a un numero fisso) Non mi sembra di averlo capito. Non ho potuto trovare la ragione o la prova per questo. Non so se si tratta di un algoritmo denominato.

algorithms big-o

posta RE60K 30.05.2016 - 15:26

fonte

3 risposte

1

So che è tardi, ma ci vado,

La mia soluzione è ricorsiva, con due opzioni per ogni chiamata di funzione,

Se la matrice soddisfa già la condizione t, restituisce la sua lunghezza
altrimenti ci sono due opzioni per generare una sottosequenza, rimuovere un elemento dall'inizio o rimuovere ed elemento dalla fine. Quindi, invochi la stessa identica funzione in modo ricorsivo per entrambe le opzioni, restituisce la lunghezza massima delle due.
```
def search_subs(a, k):
   #print "array is: ", a
   if sum(a) <= k:
       return a.__len__()
   else:
       return max(search_subs(a[1:], k), search_subs(a[:-1], k))

print search_subs([2,2,3], 3)
```

La complessità del caso peggiore è O (n ln n), credo.

risposta data 16.08.2017 - 10:47

fonte

0

Invece di chiedere "perché funziona l'ultimo approccio", dovresti chiedere "funziona l'ultimo approccio". Non è così. start viene incrementato di 1 esattamente una volta in ogni iterazione del ciclo, e curr_sum sarà uguale a 0 dopo che l'avvio è aumentato. Questo non troverà mai una soluzione a meno di sum == 0.

Sospetto strongmente che ci debba essere qualche istruzione "while" prima del codice che sottrae [start] alla matrice e aumenta l'avvio.

risposta data 30.05.2016 - 16:09

fonte

Leggi altre domande sui tag algorithms big-o

flusso di lavoro git di piccole dimensioni Vantaggi dei server di applicazioni Java a pagamento? [chiuso]

score 2 · Accepted Answer

Ora hai corretto il post, raramente è una buona idea cercare di capire un algoritmo dall'implementazione. È molto più facile sviluppare l'algoritmo e il codice.

Iniziamo con una cosa semplice: data una posizione iniziale in un array, quanti elementi di array possiamo aggiungere dalla posizione di partenza in modo che la somma non sia maggiore di t? Cioè, dato un indice 'start', trova un indice 'end' ≤ n, in modo che array [start] + array [start + 1] + ... + array [end - 1] ≤ t, e uno dei due estremi = n o l'aggiunta di array [end] renderebbe la somma > t.

È abbastanza semplice. Dato inizio, scriviamo

end = start; 
sum = 0; 
while (end < n && sum + array [end] <= t) {
    sum += array [end];
    end += 1;
}

Semplice, ma può essere lento. Supponiamo di avere n = 1.000.000, t = 1.000.000 e tutti gli elementi dell'array sono 1 o 2, sommeremo sempre almeno mezzo milione di valori e quello per un milione di possibili valori di inizio.

Quando controlliamo il valore successivo start + 1, sappiamo che la somma degli elementi dell'array dalla matrice [start] all'array [end - 1] è ≤ t, quindi poiché array [start] ≥ 0 sappiamo anche che il la somma dell'array [start + 1] su array [end - 1] è ≤ t. E calcoliamo la somma in una operazione sottraendo la matrice [start] dalla somma corrente. Quindi per calcolare "fine" per ciascuno dei valori di inizio, usiamo questo codice:

end = 0;
sum = 0;
for (start = 0; start < n; ++start) {
    while (end < n && sum + array [end] <= t) {
        sum += array [end];
        end += 1;
    }
    /* Do something with start, end, sum */
    sum -= array [start];
}

Quando start = 0, facciamo la stessa cosa della prima versione. Per n maggiori, iniziamo il ciclo interno con un valore per fine non troppo grande e la somma fino a quel punto correttamente sommata. Ovviamente ora puoi facilmente fare cose come trovare la somma più grande, trovare la somma con il numero più grande o più piccolo di elementi e così via.

Il tempo di esecuzione è O (n), poiché sia l'inizio che la fine sono aumentati di 1 esattamente n volte.