Riguardo "Festa di laurea"

Buon pomeriggio, ancora una volta chiedo aiuto qui sul forum, vogliate perdonarmi.
Dopo un po’ di problemi in cui applicarla non era subito stata la mia primissima idea, questa volta ho dedicato sin da subito tempo ad un’implementazione in stile dynamic programming per risolvere Festa di Laurea (luiss_laurea). Ho di proposito evitato di creare una soluzione che facesse uso di bruteforce per il puro spirito di allenarmi (ditemi tranquillamente se è una perdita di tempo cercare una soluzione che non sia di questo tipo, tenendo sempre conto del fatto che potrebbe anche non esistere).

Ci sarei anche riuscito tranquillamente, se solo non fosse che poi ho trovato vari controesempi e contraddizioni per ciò che stavo per implementare.

L’algoritmo che avevo in mente era il seguente:

  • Fai un ciclo da 0 a n escluso (variabile iterativa: i):
    • Prendi un mezzo già in uso con posti disponibili se possibile, altrimenti scegli un altro mezzo che abbia prezzo minore.
    • Rimuovi un posto dal mezzo ed aggiorna il costo minimo per il numero di persone, aggiungendo al prezzo per i-1 persone (se i>0, altrimenti il prezzo da usare è 0) il prezzo pagato per noleggiare un altro mezzo (se noleggiato).

L’algoritmo sopracitato è palesemente sbagliato, in quanto non terrebbe conto di numerosi fattori.


Problema 1

Consideriamo per semplicità due soli mezzi P_1 e P_2. P_1 ha costo 5 e capienza 2, mentre P_2 ha costo 6 e capienza 3.

Secondo l’algoritmo mostrato sopra, il ciclo si svolgerebbe dunque così:

  • i=0, controllo i due mezzi e noto che il costo minimo viene dato da P_1, da cui tolgo un posto. Il costo minimo per una persona è dunque 5.
  • i=1, controllo i due mezzi e noto che il costo minimo viene sempre dato da P_1, da cui tolgo un altro posto, rendendolo quindi inutilizzabile (\because \text{capienza} = 0). Il costo minimo per due persone è ancora 5.
  • i=2, controllo i due mezzi (i posti di P_1 sono 0, quindi è inutilizzabile), prendo P_2, da cui tolgo un posto. Il costo minimo per tre persone sarebbe dunque 5 + 6 = 11…se solo non stessero così le cose.

Infatti, il costo minimo è 6, ovvero tutte e tre le persone andrebbero su P_2! Non saprei come risolvere ciò.

Problema 2

Consideriamo undici mezzi. P_1, P_2, \dots, P_{10} hanno tutti costo 1 e capienza 1, mentre P_{11} ha costo 9 e capienza 10.

Il ciclo è il seguente:

  • i=0, controllo i mezzi, P_1 è il migliore; il prezzo minimo è 1 e P_1 non è più utilizzabile.
  • i=1, controllo i mezzi, P_2 è il migliore; il prezzo minimo è 1 + 1 e P_2 non è più utilizzabile.
  • \dots
  • i=k, controllo i mezzi, P_{k+1} è il migliore; il prezzo minimo è k+1 e P_{k+1} non è più utilizzabile.
  • \dots
  • i=9, controllo i mezzi, P_{10} è il migliore; il prezzo minimo è 10 e P_{10} non è più utilizzabile.

Sbagliato anche qui! Tutte e dieci le persone potrebbero andare tranquillamente su P_{11} e pagare solo 9 al posto di 10.


Ringrazio tutti in anticipo e chiedo venia per la lunghezza e la profondità dei miei dubbi.

Avendo tempo illimitato ogni cosa che provi è buona per allenamento. Cosi se ti capiterà un problema simile sai già cosa fare o non.
Per quanto riguarda le soluzioni bruteforce non sono del tutto da ignorare, una grande capacità è saper usare al proprio vantaggio le assunzioni e capire la complessità desiderata per il punteggio pieno.

Una bruteforce con memorizzazione è sempre una dp :new_moon_with_face:
Piccola sfida per quando risolverai il problema:

Riusciresti a risolvere il problema con O(1) di memoria?

1 Mi Piace

Ti ringrazio ancor prima di cominciare a scrivere il post.

Ottimo consiglio, ne terrò in conto durante i miei umili “allenamenti”.

In effetti hai ragione, in gara avrei assolutamente provato a costruire una soluzione bruteforce . Ciononostante, comprendere la migliore soluzione in termini assoluti, credo sia un’ottima cosa.

Provo ad implementarlo, allora!