Somma di sottoinsiemi e partizionamento
Raggiungere un obiettivo con un sottoinsieme scelto
Somma di sottoinsiemi e partizionamento è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 4 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 Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
La domanda del subset sum
Dati alcuni numeri e un obiettivo, esiste un sottoinsieme la cui somma è esattamente quell'obiettivo? È un problema di zaino in cui valore e peso coincidono.
DP booleana, non valore
Qui si tiene traccia della raggiungibilità, non di un massimo. Definisca dp[s] come True quando un sottoinsieme ha somma esattamente pari a s.
dp = [False] * (target + 1)
dp[0] = TrueZero è sempre raggiungibile
Il sottoinsieme vuoto ha somma zero, quindi dp[0] inizia con valore True. Ogni altra somma inizia con valore False, finché un numero non dimostra che è raggiungibile.
La transizione
Per ogni numero, contrassegni s come raggiungibile se s - num lo era già. Un singolo numero può trasformare in True molte somme.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Ancora all'indietro
Ogni numero può essere usato al massimo una volta, quindi il ciclo interno procede all'indietro, proprio come nello zaino 0/1. Procedere in avanti riutilizzerebbe un numero.
Leggere il verdetto
Dopo aver elaborato tutti i numeri, dp[target] fornisce la risposta. True significa che esiste un sottoinsieme valido; False significa che è impossibile.
Il problema della partizione
Il problema della partizione chiede: è possibile dividere l'array in due parti con la stessa somma? Si riduce direttamente al subset sum.
Dimezzare il totale
Se la somma totale è dispari, due metà uguali sono impossibili, quindi la risposta è subito negativa. Altrimenti l'obiettivo è semplicemente total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Riutilizzare il subset sum
Ora basta verificare se un sottoinsieme raggiunge total // 2. Se una metà raggiunge l'obiettivo, il resto forma automaticamente la seconda metà corrispondente.
La complessità
Il costo è dell'ordine di n per target, un limite pseudopolinomiale. È rapido quando l'obiettivo è piccolo e lento quando le somme sono enormi.
Una famiglia di problemi
La somma di sottoinsiemi, la partizione e lo zaino 0/1 condividono lo stesso motore. Riconosca la struttura prendere o lasciare e potrà riutilizzare lo stesso ciclo.
Verifica rapida
Verifichi la riduzione della partizione.
Riepilogo
Ha risolto la somma di sottoinsiemi con la programmazione dinamica booleana e un ciclo all'indietro, poi ha ridotto partition al raggiungimento di total // 2. Stesso motore, nuovi risultati. ✅
Domande Frequenti
La lezione «Somma di sottoinsiemi e partizionamento» è gratuita?
Sì — il testo completo di «Somma di sottoinsiemi e partizionamento» è 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 Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Somma di sottoinsiemi e partizionamento»?
Raggiungere un obiettivo con un sottoinsieme scelto Eserciti Competitive Programming Academy 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 Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Somma di sottoinsiemi e partizionamento»?
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 Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy 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
- Knapsack 0/1: prendere o lasciare
- Knapsack ottimizzato nello spazio
- DP illimitato e cambio di monete
- Somma di sottoinsiemi e partizionamento