Zaino frazionario in tempo lineare

Sarebbe carino se tu dicessi il problema. Presumo che tu abbia $ n $ elementi $ x_i $ , ciascuno con profitto $ p_i $ e weight $ w_i $ . Vuoi massimizzare il tuo profitto con il vincolo che il peso totale sia al massimo $ W $ . Per ogni elemento $ x_i $ , puoi inserire qualsiasi frazione $ \ theta \ in [0,1] $ di esso, che ti darà profitto $ \ theta p_i $ e peso $ \ theta w_i $ .

Ecco un esempio. Hai oro grezzo, con un profitto di $ 1000 $ e peso $ 1 $ . Hai anche delle banane, con un profitto di $ 1 $ e peso $ 10 $ . Supponi di poter portare un peso di $ 2 $ . Cosa faresti? Naturalmente, prima metti più oro che puoi, cioè tutto, e poi lo metti quante più banane puoi, cioè un decimo, per un profitto totale di $ 1000.1 $ .

Lalgoritmo generale è simile. Supponi di dividere $ W $ in un $ 1000 $ “slot”, che desideri riempire con il massimo parti redditizie dellarticolo di peso $ W / 1000 $ . Per un articolo che pesa $ w_i $ , abbiamo $ w_i / (W / 1000) $ pezzi (supponiamo per il momento questo è un numero intero), e ciascuno di essi vale $ p_i / (w_i / (W / 1000)) $ . Quando si sceglie cosa mettere in uno slot, vorremmo massimizzare il nostro profitto, quindi scegliamo lelemento con il massimo $ p_i / w_i $ e lo mettiamo come tanti pezzi possibili. Se finiamo, scegliamo lelemento con il successivo $ p_i / w_i $ più grande e così via.

Puoi implementarlo senza dividere $ W $ in un $ 1000 $ pezzi: scegli lelemento con $ p_i / w_i $ e inseriscilo il più possibile. Se finisci, scegli il prossimo e mettine il più possibile. E così via. Limplementazione di questo algoritmo richiede lordinamento dellelenco $ p_i / w_i $ , che richiede tempo $ O (n \ log n) $ . Lalgoritmo che descrivi utilizza lo stesso trucco utilizzato in quickselect per ridurre il tempo di esecuzione a $ O (n) $ , a costo di rendere lalgoritmo randomizzato.

Suggerisco il seguente percorso per comprendere lalgoritmo:

1. Comprendere il classico algoritmo avido per lo zaino frazionario.
2. Comprendere quickselect.
3. Guarda come lalgoritmo che citi combina la tecnica della selezione rapida con lapproccio avido.

R è l insieme di rapporti di profitto / peso di ogni oggetto , dove vengono forniti il profitto e il peso degli oggetti. E W è la Capacità dello zaino .
Ora invece di scegliere un elemento casuale in una sola fase, possiamo applicare l algoritmo di ricerca mediana trova la mediana tra O (n) volte.
Quindi possiamo eseguire il resto di tutti i passaggi.Quindi lanalisi della complessità temporale sarà:
        T (n) = T (n / 2) + O (n).
E otterremo O (n) come soluzione. Dimmi se qualcosa non è spiegato correttamente e vuoi saperne di più.

In tempo lineare, puoi trovare il elemento mediano in termini di valore per unità di peso. Quindi, anche in tempo lineare, puoi capire se puoi inserire tutti gli oggetti che sono almeno così preziosi nello zaino o meno. Se puoi, fallo e risolvi ricorsivamente il problema per gli n / 2 elementi di valore inferiore dato che tu ” ho già riempito lo zaino. Se non puoi, puoi gettare gli n / 2 elementi di valore inferiore, e quindi provare a risolvere nuovamente il problema con solo gli n / 2 di valore più elevato.

La ricorrenza qui è T (n) = T (n / 2) + O (n) e abbiamo quello T (n) = O (n) , come desiderato.

Nella soluzione hai incollato: R è linsieme di rapporti, profitto / peso W è la somma dellintero peso di questo insieme , utilizzato per confrontare la capacità del tuo zaino. Allo stesso modo, {pi / wi | pi / wi} rappresenta li esimo elemento il profitto è li esimo valore di peso. Stiamo confrontando questo valore con il valore r selezionato a caso e quindi lo separiamo in base al confronto del rapporto. I R1, R2, R3 sono ulteriori sottoinsiemi del rapporto impostato a seconda che il rapporto sia minore, uguale o maggiore di quello di lelemento mediano.

allo stesso modo, i S1, S2, S3 sono la somma dei pesi di questi insiemi.

Ora scegli la soluzione adatta impostata in base ai valori del rapporto come spiegato allinizio.