La mia soluzione di forza bruta è troppo lenta, necessaria soluzione DP [chiusa]

L'OP ha osservato in un commento che ha trovato il problema etichettato come "forza bruta e DP". Che è assolutamente ridicolo. Ecco la soluzione temporale lineare:

1. Osservare che l'ordine di a, b, c è del tutto irrilevante, quindi ordinali per fare un ≥ b ≥ c.

2. Calcola g = gcd (a, b, c) (massimo comun divisore). Se n non è divisibile per g allora non c'è soluzione. Altrimenti, dividere a, b, c e n per g. Ora gcd (a, b, c) = 1.

3. Calcola g = gcd (b, c), che significa n - ai deve essere un multiplo di g. Trova i0 = il più piccolo i tale che n - ai sia un multiplo di g. Tale i esiste perché gcd (a, g) = 1. I valori possibili per i che possono portare a soluzioni sono i0, i0 + g, i0 + 2g e così via. Se n - a * i0 < 0 allora non c'è soluzione.

4. Dividi b e c per g. Ora dobbiamo trovare j, k che risolva (n - ai) / g = bj + ck, per i = i0, i0 + g, i0 + 2g e così via. gcd (b, c) è ora 1. Per ognuno di questi, sia m = (n - ai) / g, allora abbiamo bisogno di bj modulo c = m modulo c. Poiché gcd (b, c) = 1, c'è un j0 ≥ 0 più piccolo che risolve questa equazione. Gli altri valori per risolvere questo j0 + c, j0 + 2c, j + 3c. Tuttavia, ogni volta che aumentiamo j per c, dobbiamo ridurre k per b, e poiché b ≥ c questo non può migliorare la soluzione. Abbiamo k = (m - b * j0) / c, e questo k deve essere ≥ 0. L'aumento di j non può rendere k ≥ 0 se è minore di 0 per un j più piccolo. Ciò significa che per un dato i, scegliamo j = il più piccolo j tale che bj modulo c = m modulo c, e k = (m - b * j0) / c.

5. Per trovare j0 velocemente, creiamo una tabella di ricerca T mappando un valore di modulo m alla j più piccola con bj modulo c = m. Ciò avviene in tempo lineare calcolando b * 0 modulo c, b * 1 modulo c ecc. E impostando T [b * t modulo c] = t per 0 ≤ t < c.

6. L'algoritmo ora inizia con i = i0 e nessuna soluzione trovata finora. Se n - ai < 0 quindi tornare con la migliore soluzione trovata finora. Altrimenti lasciamo m = (n - ai) / g. Sia j = T [m modulo c], k = (m - b * j) / c. Se k ≥ 0 e i + j + k è meglio della soluzione migliore finora abbiamo trovato una nuova soluzione migliore. Altrimenti continua con i sostituito con i + g.

7. Acceleriamo l'algoritmo osservando che dopo aver calcolato m, sappiamo che i + j + k ≤ i + m / c che non aumenta mai. Quindi, se troviamo una soluzione e i + m / c non è maggiore di quella soluzione, possiamo uscire dall'algoritmo perché sappiamo di aver trovato una soluzione che non può essere ulteriormente migliorata.

Con l'input n = 4000, a, b, c = 1, 2, 3: riorganizziamo a = 3, b = 2, c = 1. gcd (a, b, c) = 1 so a, b , c, n rimangono invariati. g = gcd (b, c) = 1, quindi b, c sono invariati, la tabella T contiene un valore T [0] = 0.

Lasciamo i = 0, e n - ai è divisibile per g = 1. Quindi iniziamo con i = 0, m = 4000, j = T [0] = 0, k = (4000 - j * b) / c = 4000, dando la soluzione i = 0, j = 0, k = 4000.

Quindi lasciamo i = 1, m = 3997. i + m / c = 3998 < 4000, quindi la soluzione che abbiamo trovato prima è ottimale. Quindi il problema che ha superato il limite di tempo è in realtà così semplice che posso scrivere il calcolo completo. (BTW se c = 1 dopo aver diviso a, b, c, n per gcd (a, b, c), allora i = 0, j = 0, k = n, è sempre la soluzione ottimale).

Penso che la soluzione potrebbe essere sub-lineare nel tempo se troviamo O più veloce O (g) usando l'algoritmo di Euclide, e invece di costruire una tabella T in O (c) trova i valori j usando l'algoritmo di Euclide, sperando che possiamo dimostrare rapidamente che una soluzione trovata è ottimale.

Fai il terzo ciclo: è assolutamente inutile. Controllate se (a * i + b * j + c * k) == n. Ciò significa che k deve essere uguale a (n - a * i - b * j) / c. Quindi un cambiamento banale è calcolare solo questo k e verificare se è una soluzione.

Ordina a, b, c tale che a ≥ b ≥ c. Ora è ovvio che con la crescita di j, k deve ridursi tanto o più, quindi la somma j + k non può crescere. Ciò significa che se trovi un valore per k dato i e j, non devi preoccuparti di controllare j più grandi. La somma i + j + k non diventerà più grande.

Successivamente esaminerei l'algoritmo di Euclids per trovare le soluzioni di bj + ck = n - ai. E alla fine, puoi stimare quanto potrebbe essere grande i + j + k man mano che divento più grande. Di nuovo, la somma tenderà ad essere inferiore se diventerò più grande, e quando sarò abbastanza grande sarai in grado di dimostrare che la somma non può diventare più grande.

Suppongo che nel caso l''insieme di problemi minori' sarà:

• massimizza (i, j, k) per n - x dove x è un numero più difficile calcolare

. dalla cima della mia testa, vorrei calcolare:

n mod a, n mod b, n mod c

assegnandomi un set di x per il quale posso massimizzare facilmente il corrosivo i, j o k ie

(n - (n mod a)) / i ecc.

e memorizzarli insieme al resto, x in una struttura ad albero

Quindi, per ogni risultato, calcola:

(n mod a) mod b, (n mod a) mod c ecc

di nuovo memorizzando il resto e l'intera frazione nei nodi dell'albero al di sotto del primo risultato.

Una volta raggiunta la fine di ciascun percorso, puoi eseguire il ciclo attraverso l'albero per calcolare il risultato massimizzato per n, sommando efficacemente max (n-x) + max (x)

Vale per n = 13, a = 2, b = 3

13 mod 2 = 6 remainder 1
    1 mod 3 = no solution
13 mod 3 = 9 remainder 4
    4 mod 2 = 2 remainder 0

i = 3, j = 2

Per la ricorsione, puoi ridefinire il tuo problema iniziale  f (n, a, b, c) dove ai + bj + ck = n a  f (n, a, b, c) = ai + f (n-ai, b, c) dove  f (n, a) diventa trovando divisori di n. Posso aggiungere più dettagli se sei interessato. Rispondere al cellulare è una sfida.

Per rispondere alla tua domanda "DP": questa operazione può essere eseguita in tre passaggi:

1. Trova le soluzioni per a*i==m , dove 1<=m<=n : questo è semplice, basta controllare se m%a==0 , quindi la soluzione è i = m / a. Se no, allora non c'è soluzione. Memorizzali in un array.

2. Trova le soluzioni per a*i + b*j==m dove 1<=m<=n , massimizzando (i + j): loop su tutto j con 1<=j<=m/b , solve a*i == m-b*j usando i risultati del passo 1. Per ogni m, mantieni la coppia (i, j) che ha la somma massima. Se hai bisogno solo delle somme come risultato, sarà sufficiente mantenere la somma (i + j) in un array.

3. Infine, risolvi a*i + b*j + c*k==n eseguendo il ciclo su tutti i k e utilizzando il passaggio 2 per ottenere la soluzione su a*i + b*j == n - c*k; maximize(i+j) . Mantieni la tripla (i, j, k) con la somma massima.