Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

uno,Matrice bidimensionale

1、equazione di transizione di stato：

• Non inserire oggetti : Dedotto da dp[i - 1][j], ovvero la capacità dello zaino è j e il valore massimo dell'oggetto i non è inserito in esso. In questo momento, dp[i][j] è dp[i -. 1] [j]. (Infatti, quando il peso dell'oggetto i è maggiore del peso dello zaino j, l'oggetto i non può essere messo nello zaino, quindi il valore nello zaino è sempre lo stesso di prima.)
• Metti l'oggetto i: Dedotto da dp[i - 1][j - peso[i]], dp[i - 1][j - peso[i]] è la capacità massima dello zaino senza l'oggetto i quando la capacità è j - peso[ i], allora dp[i - 1][j - peso[i]] + valore[i] (il valore dell'oggetto i) è il valore massimo ottenuto mettendo l'oggetto i nello zaino

Quindi la formula ricorsiva: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valore[i]);

2. Inizializzazione

(1) Partendo dalla definizione di dp[i][j], se la capacità dello zaino j è 0, cioè dp[i][0], indipendentemente dagli articoli selezionati, il valore totale dello zaino deve essere 0.

(2) Equazione di transizione di stato dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valore[i]); visto che i deriva da i-1, quindi deve essere inizializzato quando i è 0.

dp[0][j], ovvero: i è 0, quando si memorizza l'articolo numero 0, il valore massimo che uno zaino di ciascuna capacità può contenere.

Allora è ovvio che quando j < peso[0], dp[0][j] dovrebbe essere 0, perché la capacità dello zaino è inferiore al peso dell'articolo numerato 0.

Quando j >= peso[0], dp[0][j] dovrebbe essere valore[0], perché la capacità dello zaino è sufficiente per contenere l'articolo numero 0.

for (int j = 0 ; j < weight[0]; j++) {
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

(3) Altra inizializzazione dell'indice:

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - peso[i]] + valore[i])

dp[1][1] = max(dp[0][1], dp[0][1- peso[i]] + valore[i]) deve essere a sinistra e sopra di esso,

Pertanto, deve essere inizializzato e può essere impostato su qualsiasi valore. Per comodità, viene inizializzato su 0 per impostazione predefinita.

2. Monodimensionale (array mobile)

1. Nell'array unidimensionale dp, dp[j] significa: uno zaino con una capacità di j può trasportare oggetti con un valore massimo di dp[j]

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

2. Inizializzazione

(1) dp[0]=0, perché il valore massimo degli oggetti trasportati da uno zaino con capacità pari a 0 è 0.

(2) Supponiamo che il valore degli elementi sia maggiore di 0,Per non essere sovrascritto dal valore iniziale, quindi d.pInizializzazione dell'arrayQuando , sono tutti inizialmente 0

3. Ordine di attraversamento

Attraversare in ordine inverso

Spiegazione 1: Il valore alla fine dell'elenco deve essere determinato confrontandolo con il valore precedente ottenuto attraversando il livello precedente.

Spiegazione 2: C'è solo uno zaino 01 per ogni zaino Il fatto che questa borsa sia posizionata o meno è correlato allo stato della borsa precedente. L'array a sinistra è una quantità che descrive lo stato della borsa precedente e il numero relativo quello a destra è uno stato in sospeso del bagaglio corrente. Nel codice, il numero a sinistra è necessario per determinare l'array a destra, quindi il numero a sinistra non può essere distrutto prima che venga calcolato il numero a destra.

Spiegazione 3: Per due dimensioni, il risultato di ogni nuovo numero dp che ho viene dall'alto e da sinistra; infatti, dovrebbe essere così in una dimensione, ma in una dimensione, se è ancora da sinistra a destra, allora la mia sinistra effettiva I dati sono stati aggiornati ( Il lato sinistro non è più il lato sinistro “originale”!Ciò causerà alcuni doppi conteggi ), anche se la cima è ancora quella originale, il numero ottenuto non è corretto.E se attraversiamo da destra a sinistra nello strato dello zaino (strato interno), allora lo sarà sempre l'elemento a sinistraNon verrà sovrascritto con nuovi valori a causa della mia precedente operazione., in modo da ottenere il valore corretto.

3. Applicazione

1. Dato un array non vuoto contenente solo numeri interi positivi. È possibile dividere questo array in due sottoinsiemi in modo che la somma degli elementi dei due sottoinsiemi sia uguale?

Nota: gli elementi in ogni array non supereranno 100 e la dimensione dell'array non supererà 200

Esempio 1:

• Ingresso: [1, 5, 11, 5]
• Risultato: vero
• Spiegazione: L'array può essere diviso in [1, 5, 5] e [11]

analizzare:

L'articolo è io,

Il peso è nums[i], anche il valore è nums[i] e il volume dello zaino è sum/2.

Simile allo zaino 01

Equazione di transizione di stato:

dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
    for(int j = target; j >= nums[i]; j--) {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;

2. C'è una pila di pietre e il peso di ciascuna pietra è un numero intero positivo.

Ad ogni round, scegli due rocce qualsiasi e fracassale insieme. Supponiamo che i pesi delle pietre siano rispettivamente xey e x <= y. Quindi i possibili risultati della frantumazione sono i seguenti:

Se x == y, allora entrambe le rocce saranno completamente frantumate;

Se x != y, allora la pietra di peso x si frantumerà completamente e la pietra di peso y avrà un nuovo peso di yx.

Alla fine resterà al massimo una sola pietra. Restituisce il peso più piccolo possibile di questa pietra. Se non sono rimaste pietre, restituisci 0.

Esempio:

• Ingresso: [2,7,4,1,8,1]
• Uscita: 1

analizzare:

Prova a dividere le pietre in due mucchi dello stesso peso, in modo che dopo la collisione rimanga la pietra più piccola

Quindi dividilo in due pile di pietre. Il peso totale di una pila di pietre è dp[bersaglio] e il peso totale dell'altro mucchio è sum - dp[bersaglio].

Quando si calcola il target, target = sum / 2 perché è arrotondato per difetto, quindi sum - dp[target] deve essere maggiore o uguale a dp[target]

Quindi il peso minimo della pietra rimasta dopo la collisione è (sum - dp[target]) - dp[target]

for (int i = 0; i < stones.length; i++) {
//采用倒序
    for (int j = target; j >= stones[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
    }
}
//结果
sum - 2 * dp[target];

citato da:Codice Note Casuali