Salve. Mi stavo esercitando con degli algoritmi per le gare territoriali di domani:
Ci troviamo in un caso particolare di uso di un algoritmo Greedy, ricorsivo. I casi vanno a buon fine, fino però ad uno in particolare. Il caso, in particolare, mostra una lista di valori (values) uguali, che una volta trattati, mandano in loop il programma. Ho provato diverse soluzioni, ma nessuna mi ha portato alla risoluzione. Qualche aiuto? posso allegare parte del codice usato per rendere l’idea? Grazie a tutti per la lettura e per la pazienza nella risposta!
Non ho capito benissimo cosa stai cercando di risolvere/fare.
Knapsack 0-1 è dp
Nel caso invia il codice affinché possa comprendere meglio
def knapsack(soldi, value, cores, n):
if n == 0 or soldi == 0:
return 0
if (value[n - 1] >= soldi):
return knapsack(soldi, value, cores, n - 1)
else:
return max(cores[n - 1] + knapsack(soldi - value[n - 1], value, cores, n - 1), knapsack(soldi, value, cores, n - 1))
#la variabile "soldi" sarebbe la variabile "weight"
soldi = 45280856
#i values sarebero i "weights" da sottrarre alla variabile "soldi"
value = [1882109, 9425843, 9126748, 6699986, 8154877, 3366129, 408021, 1712767, 1306387, 2258269, 5044411, 8702136, 620895, 117161, 4773245, 4410347, 8009624, 2729075, 4035993, 3772200, 8054116, 2998497, 2042550, 4471384, 6478269, 1815674, 2055811, 2555122, 2935983, 4232869, 2098585, 6617023, 6840497, 6541448, 6233332, 1835304, 9450039, 7068401, 5181027, 5469793, 3843332, 3540483, 2775959, 4505383, 8347589, 1175712, 1054225, 8678226, 6936636, 2492701, 5873721, 9534298, 3519678, 1580393, 5126078, 7946862, 2830957, 6147042, 3465848, 9639915, 6399790, 3530903, 2566271, 9949933, 9369481, 2339011, 5764748, 4567359, 7433996, 3416114, 2702526, 6242650, 5968625, 2154614, 3064344, 8384513, 3437777, 9987734]
#i cores sarebbero il valore rispetto al peso. Come si nota, sono tutti uguali
cores = [79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79, 79]
print(knapsack(soldi, value, cores, len(value)))
ecco a te. Cosa intendi con la frase “Knapsack 0-1 è dp”?
Knapsack 0-1 sarebbe prendo o no l’oggetto (e posso prenderlo massimo una volta). Dp è programmazione dinamica
Oh, comprendo, comprendo. Beh, allora non sono andato molto lontano con il mio codice, hahaha. Ma tornando al problema, ha qualche suggerimento?
dammi 5 min e vedo
comunque te lo fai completamente ricorsivo e dunque ti ritrovi a ricalcolare a volte gli stessi risultati che hai già calcolato
Dice? Ha qualche suggerimento per migliorarlo?
allora per prima cosa
qui la condizione dovrebbe essere solo maggiore
puoi creare una matrice di dimensioni [ n elementi + 1 ] [ maxBudget + 1 ], la inizializzi tutta a 0 e semplicemente prima di fare return, fai assumere a Matrice [ n ] [ soldi ] il valore che dovresti restituire
sto runnando il codice ma non ha ancora finito di computare, per curiosità quanto ti ci mette a te?
È qui che sorge il problema. Va in loop e non so perché…
senno solitamente quanto ci metterebbe? essendo completamente ricorsivo è esponenziale
Con gli altri casi meno di 1 secondo, un lasso di tempo davvero basso. Devi sapere che il codice che ti ho mostrato rappresenta il quinto caso su 27. I primi 4 li ha fatti in tempi brevissimi, ma al 5 parte il loop
la tua complessità sarebbe di O(2^N)
il tuo N in quel caso è 78 dunque 2^78 che equivale a circa 3*10^23
Quindi capisco che più i casi sono grandi, esponenzialmente grande è la complessità. Quindi questo algoritmo non va molto bene, vero?
cosi com’e` no
se vuoi posso aiutarti a farti capire come ottimizarlo oppure darti direttamente soluzioni/spiegazioni etc etc
Gradirei una soluzione passo passo in cui mi spieghi basicamente cosa accade. È la prima volta che approccio questi algoritmi, quindi sarebbe effettivamente gradita una soluzione spiegata, cosi’ che possa imparare per applicarla in futuro agli algoritmi che mi verranno sottoposti, sempre le va bene
vaa bene, per iniziare il tuo algoritmo non occupa spazio per i risutati(oltre alle chiamate nello stack delle ricorsive e gli array con i valori iniziali) ma risulta estremamente lento
per esempio pensa alla sequenza di Fibonacci: puoi farla ricorsiva o iterativa;
iterativa non hai problemi, ma puramente ricorsiva se noti (se vuoi ti faccio uno schema per capire meglio) a volte richiamerai il valore di un numero già calcolato ma che però ricalcolerà