Sottoinsieme più piccolo di array la cui somma non è inferiore alla chiave

Question

Dato un array (se si assumono numeri interi non negativi) ci viene richiesto di trovare il sottoinsieme di lunghezza più piccolo tale che la somma di elementi non sia minore di K. K è un altro intero fornito come input.

È possibile avere una soluzione con complessità temporale O (n) [big oh di n]?

il mio pensiero corrente è lungo le seguenti linee: potremmo ordinare l'array in O (n * log n) e quindi scorrere l'array ordinato a partire dal numero più grande e mantenere la somma in esecuzione fino a che la somma in esecuzione diventa> = K.

Tuttavia, questo avrebbe il tempo di esecuzione peggiore di O (n * (log n + 1)).

Quindi, se qualcuno potesse condividere idee di fare questo in tempo O (n), sarei davvero grato ..

Nota: Gli elementi del sottoarray non dovete essere una sequenza contigua della matrice originale, in questo contesto

Answer 1

C'è un algoritmo di tempo lineare per trovare i maggiori numeri K - http://en.wikipedia.org/wiki/Selection_algorithm. Ovviamente quello che vuoi è solo un numero maggiore di numeri per riassumere almeno K.

Nell'algoritmo di selezione standard, fai un pivot casuale e poi guarda per vedere quanti numeri cadono su ciascun lato di esso. Quindi accettate o rifiutate una metà e continuate a lavorare sull'altra metà. Hai appena guardato ciascun numero in ogni metà, a sua volta - il costo di ogni stadio di rotazione è lineare, ma la quantità di dati considerati in ogni fase si riduce abbastanza rapidamente che il costo totale è ancora solo lineare.

Il costo di uno stadio di rotazione sarà ancora lineare solo se si prende la somma di tutti i numeri sopra il pivot. Usando questo, puoi allenarti se accettare tutti questi numeri, insieme ai numeri precedentemente selezionati, ti darebbe una raccolta di numeri che si sommano almeno a K. Se lo fa, puoi abbandonare gli altri numeri e usare i numeri sopra il perno per il prossimo passaggio. In caso contrario, puoi accettare tutti i numeri sopra il pivot e utilizzare i numeri sotto il pivot per il passaggio successivo. Come con l'algoritmo di selezione, il pivot stesso e ogni legame ti danno alcuni casi speciali e la possibilità di trovare una risposta esatta in anticipo.

(Quindi penso che si possa fare questo in tempo lineare (randomizzato) usando una versione modificata dell'algoritmo di selezione in cui si guarda la somma dei numeri sopra il pivot, invece di quanti numeri sono sopra il pivot.

Answer 2

Questo sembra essere un problema per la programmazione dinamica. Quando si costruisce la matrice, si costruisce un altro array contenente la somma cumulativa fino a ciascun indice particolare. Quindi ogni i in quell'array ha le somme da 1..i.

Ora è facile vedere che la somma dei valori per gli indici p..q è SUM(q) - SUM(p-1) (con il caso particolare che SUM(0) è 0). Ovviamente sto usando indici basati su 1 qui ... Questa operazione è O (1), quindi ora hai solo bisogno di un algoritmo O (n) per trovare quello migliore.

Una soluzione semplice è tenere traccia di un p e di q e passarli attraverso l'array. Si espande con q per iniziare. Quindi contragga p ed espandi ripetutamente q, come un bruco che striscia nell'array.

Per espandere q:

p <- 1 
q <- 1 

while SUM(q) - SUM(p-1) < K 
    q <- q + 1 
end while 

Ora q è nella posizione in cui la somma sottoarray ha appena superato (o è uguale a) K. La lunghezza del sottoarray è q - p + 1.

Dopo il ciclo q si verifica se la lunghezza della sottostruttura è inferiore al valore corrente. Quindi fai avanzare di p di un passo (in modo da evitare di saltare accidentalmente la soluzione ottimale) e riprovare.

Non hai davvero bisogno di creare l'array SUM ... Puoi semplicemente costruire la somma della sottomarca mentre vai ... Dovresti tornare a usare il 'vero' p invece di quello appena prima .

subsum <- VAL(1) 
p <- 1 
q <- 1 

while q <= N 
    -- Expand 
    while q < N and subsum < K 
     q <- q + 1 
     subsum <- subsum + VAL(q) 
    end while 

    -- Check the length against our current best 
    len <- q - p + 1 
    if len < bestlen 
     ... 
    end if 

    -- Contract 
    subsum <- subsum - VAL(p) 
    p <- p + 1 
end while 

Note:

j_random_hacker detto: sarebbe utile per spiegare esattamente il motivo per cui è accettabile per esaminare solo la O (n) sottoarray distinte che questo algoritmo esamina, invece di tutti O (n^2) possibili sottoarray distinti

La filosofia di programmazione dinamica è:

1. non seguire percorsi di soluzione che porteranno a un risultato non ottimale; e
2. utilizzare la conoscenza delle soluzioni precedenti per calcolare una nuova soluzione.

In questo caso un'unica soluzione candidata (alcuni (p,q) tale che p <= q) viene calcolato sommando degli elementi. Poiché questi elementi sono numeri interi positivi, sappiamo che per qualsiasi soluzione candidata (p,q), la soluzione candidata (p,q+1) sarà più grande.

E così sappiamo che se (p,q) è una soluzione minima, allora non lo è (p,q+1). Terminiamo la ricerca non appena abbiamo un candidato, e testiamo se quel candidato è migliore di quello che abbiamo visto finora. Ciò significa che per ogni p, abbiamo solo bisogno di testare un candidato. Ciò porta ad entrambi i valori p e q sempre crescenti, e quindi la ricerca è lineare.

L'altra parte di questo (utilizzando soluzioni precedenti) deriva dal riconoscimento di sum(p,q+1) = sum(p,q) + X(q+1) e allo stesso modo sum(p+1,q) = sum(p,q) - X(p). Pertanto, non è necessario sommare tutti gli elementi tra p e q ad ogni passaggio. Dobbiamo solo aggiungere o sottrarre un valore ogni volta che avanza uno dei puntatori di ricerca.

Spero che questo aiuti.

Answer 3

Ecco una soluzione che dovrebbe essere abbastanza veloce. che sto indovinando che è quasi lineare.

def solve(A, k): 
    assert sum(A) >= k 
    max_ = max(A) 
    min_ = min(A) 
    n = len(A) 
    if sum(A) - min_ < k: 
     return A 
    bucket_size = (max_ - min_)/n + 1 
    buckets = [] 
    for i in range(n): 
     buckets.append([]) 
    for item in A: 
     bucket = (item - min_)/bucket_size 
     buckets[bucket].append(item) 

    solution = [] 

    while True: 
     bucket = buckets.pop() #the last bucket 
     sum_ = sum(bucket) 
     if sum_ >= k: 
      #don't need everything from this bucket 
      return solution + solve(bucket, k) 
     else: 
      k -= sum_ 
      solution += bucket 

print solve([5,2,7,52,30,12,18], 100) 
"[52, 30, 18]" 

Answer 4

credo che "sub allineamento" termine implica una parte contigua di array (like here, un altro problema, come ad esempio

Quindi esiste un semplice algoritmo O (n) per trovare un sottarray di lunghezza minima:

Impostare due indici (a sinistra, a destra) sul primo elemento e spostarli fino alla fine dell'array. Verifica la somma tra questi indici, puntatore destro avanzato, se la somma è troppo piccola (o i puntatori sono uguali), avanti a sinistra se la somma è grande

Answer 5

L'OP ha chiarito nelle sue risposte ai commenti che il problema è trovare un sottoinsieme, NON necessariamente una sequenza contigua (il termine 'sottoarray' era certamente scarso). Quindi, credo che il metodo indicato da mcdowella sia corretto, comprendendo i seguenti passi:

Partendo da N elementi, trova l'elemento MEDIAN (cioè l'elemento -N/2) -th immaginando una matrice ordinata, che tu indossi avere e non costruire). Questo è ottenuto con l'algoritmo "Mediana delle Medie", dimostrato come O (n), vedere il ref wiki già dato e ripetuto qui: Selection algorithm, see section on the Median of Median algorithm

Avere l'elemento mediano: scansionare linearmente l'insieme completo e partizionare in " sotto "e" sopra ", nel frattempo sommando, contando e facendo tutto ciò che si desidera tenere traccia di, per ciascuna delle" metà ". Questo passaggio è (anche) O (N).

Dopo aver completato la scansione, se la "metà superiore" -somma è sopra il bersaglio (K), si dimentica tutto della metà inferiore e si ripete la procedura per la metà superiore, la cui dimensione è (approssimativamente) N/2 . Se, invece, la somma della "metà superiore" è inferiore a K, si aggiunge la metà superiore al risultato finale, si sottrae la somma da K e si ripete la procedura con la metà inferiore

Complessivamente , si elaborano insiemi di dimensioni N, N/2, N/4, N/8 eccetera, ciascuno in O (M) rispetto alle rispettive taglie M, e quindi il materiale complessivo è anche lineare in N, perché N + N/2 + N/4 + N/8 ... rimane sotto 2N.

Answer 6

la sottomatrice deve essere contiguo nella definizione di matrice.

Uso 2 puntatori (inizio, fine). inizializzarle al inizio dell'array. Traccia la somma corrente tra (inizio, fine), un d sposta fine a destra uno per uno. Ogni volta che si sposta il puntatore finale, sum = sum + array [end].

E quando somma> = destinazione, iniziare a spostare l'inizio a destra e mantenere la somma di tracciamento come somma = somma - matrice [inizio].

Mentre si sposta l'inizio a destra, continuare a controllare che la somma non sia inferiore all'obiettivo. E abbiamo anche bisogno di tracciare la lunghezza facendo length = end - start + 1, così come minLength = min (minLength, length).

Ora, quando abbiamo spostato entrambi i puntatori nel modo più corretto possibile, dobbiamo solo restituire minLength.

L'idea generale è di trovare prima una "finestra" che soddisfi la condizione (somma> = destinazione), quindi far scorrere la finestra a destra di un elemento alla volta e mantenere le dimensioni minime della finestra ogni volta che spostiamo la finestra.