Stavo cercando di fare pratica con la dp, ma nel problema “nonna” principalmente non saprei come effettuare le transizioni tra uno stato e l’altro e quindi anche come evitare di prendere nella soluzione finale lo stesso piatto più volte. Finora ho visto knapsack, il problema delle monete e longest increasing/decreasing sequence, e riesco al massimo ad applicare le stesse tecniche su altri problemi😅, quindi avreste consigli su come in generale poter arrivare ad una soluzione in dp(dal punto di vista pratico) una volta capito lo stato e le transizioni? E magari come poterlo applicare in questo caso? Grazie in anticipo
Se sei ancora alle prime armi con la DP ti consiglio di optare per la soluzione ricorsiva con la memoizzazione, che non è detto che sia la soluzione più semplice ma spesso risulta più facile da intuire, comunque per quello che riguarda li stati da individuare penso sia sufficiente basarsi anche solo sull’indice, mi spiego meglio:
Partendo da ogni posizione controlli, utilizzando solo i piatti dopo quell’indice, se sia possibile arrivare alle somma richiesta e in questo caso la confronti con le altre soluzioni.
Spero di essere stato il più chiaro possibile.
2 Mi Piace
Se hai visto knapsack e non sai risolvere nonna, non hai visto bene knapsack.
Ricordati che dp e’ una tecnica molto generale, non ti serve imparare a memoria certe dp comuni, ti serve capire come e perche’ funzionano.
1 Mi Piace
Ok ho riguardato knapsack e sono riuscito a implementarlo su questo problema, mi ero confuso all’inizio vedendo che c’erano solo i valori e non peso e valore come nel classico knapsack ma effettivamente è la stessa cosa basta capire il ragionamento… Però in questo caso come in qualche altro problema la soluzione che “combino” al mio valore che sto controllando si trova facendo il limite massimo consentito corrente(nel mio caso j che indica tutte le capacità da 1 a K) - il valore che controllo(in questo caso un piatto), quali sono per esempio altri metodi per prendere la sotto soluzione precedente da combinare con un valore(anche a livello concettuale)? Forse è una domanda stupida però credo che il mio problema sia questo