Knapsack frazionario per rapporto
Scegliere prima il valore più alto per unità di peso
Knapsack frazionario per rapporto è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Impostare il problema dello zaino
Ha a disposizione oggetti con un valore e un peso e uno zaino di capacità limitata. L'obiettivo è trasportare il maggior valore totale possibile. 🎒
Frazionaria significa divisibile
Nella versione frazionaria può prendere una parte di un oggetto, come metà di un sacco di grano. È questa libertà che permette a greedy di funzionare.
Valore per unità di peso
La metrica fondamentale è il rapporto tra il valore e il peso di ogni oggetto. Un rapporto alto indica molto valore concentrato in pochissimo spazio.
ratio = value / weightOrdinare in base al rapporto migliore
Ordini gli oggetti in base al valore per unità di peso, dal più alto al più basso. La strategia greedy consiste nel scegliere continuamente il valore più denso disponibile.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Prendere l'intero oggetto finché ci sta
Scorra la lista ordinata e prenda ogni oggetto interamente se entra ancora nella capacità rimanente. Aggiunga il suo valore completo al totale.
if weight <= cap:
total += value
cap -= weightRiempire l'ultimo spazio
Quando un oggetto è troppo grande, ne prenda una frazione che riempia esattamente lo spazio rimasto. A questo punto lo zaino è pieno e può fermarsi.
total += value * (cap / weight)Perché funziona l'ordine per rapporto
Ogni unità di capacità dovrebbe contenere il maggior valore possibile, quindi l'oggetto più denso deve essere scelto per primo. Sostituirlo con uno meno denso comporta soltanto una perdita di valore.
Il problema dello zaino 0/1 è diverso
Se gli oggetti non possono essere suddivisi, scegliere avidamente in base al rapporto non funziona. La versione 0/1 richiede la programmazione dinamica, non questo semplice ordinamento.
Il tempo di esecuzione
Ordinare in base al rapporto costa O(n log n), mentre il ciclo di riempimento è lineare. È più che sufficiente per i limiti tipici delle gare.
Attenzione alla frazione finale
Utilizzi numeri in virgola mobile o frazioni esatte per l'oggetto parziale. Troncare troppo presto può ridurre il valore e causare una risposta errata.
Dove si applica
Pensi al caricamento di merci, alla miscelazione di combustibili o alla suddivisione di risorse. Ogni volta che le parti sono divisibili, l'approccio greedy basato sul rapporto è lo strumento giusto.
Verifica rapida
Sta riempiendo una borsa nel problema dello zaino frazionario.
Riepilogo
Ordini gli oggetti in base al valore per peso, prenda gli oggetti interi finché entrano, poi aggiunga una frazione per riempire la borsa. Questo approccio greedy è ottimale solo quando gli oggetti possono essere suddivisi. 🚀
Impara Coding Interview Prep con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 90
- Lezioni
- 360
Domande Frequenti
La lezione «Knapsack frazionario per rapporto» è gratuita?
Sì — il testo completo di «Knapsack frazionario per rapporto» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Knapsack frazionario per rapporto»?
Scegliere prima il valore più alto per unità di peso Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Knapsack frazionario per rapporto»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- La mentalità greedy
- Selezione delle attività in base alla fine più anticipata
- Knapsack frazionario per rapporto
- Riconoscere quando il greedy fallisce