Missioni 60/100

Aiuto
1

Buonasera,
stavo provando a fare Missioni per cercare di comprendere meglio e applicare la programmazione dinamica, ma mi trovo bloccato a 60/100 e non capisco cosa sbaglio nel ragionamento. In particolare non vengono i testcase 1,6,7 e 8.
Qualche anima gentile saprebbe indicarmi dove sto sbagliando?

Grazie

    int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int N;
    cin >> N;
    vector<int> durata(N), scadenza(N);

    for(int i = 0; i < N; i++)
        cin >> durata[i] >> scadenza[i];

    vector<int> soluzioni(N), dataConclusione(N);

    soluzioni[0] = 1;
    dataConclusione[0] = durata[0];

    for(int j = 1; j < N; j++) {
        soluzioni[j] = 1;
        for(int i = 0; i < j; i++) {
            if(scadenza[j] - durata[j] >= dataConclusione[i]) {
                if(soluzioni[i] + 1 > soluzioni[j]) {
                    soluzioni[j] = soluzioni[i] + 1;
                    dataConclusione[j] = dataConclusione[i] + durata[j];
                } else if(soluzioni[i] + 1 == soluzioni[j] && dataConclusione[j] > dataConclusione[i])
                    dataConclusione[i] = dataConclusione[j];
            }
        }
    }

    cout << *max_element(soluzioni.begin(), soluzioni.end());

    return 0; }
2

Prova con questo input:
5
2 2
7 9
5 12
5 15
3 16

Ci sono molti topic che trattano questo problema, ti potrebbero essere di aiuto.

3

Se ho ben capito il tuo algoritmo calcola la massima sequenza ottenibile con l’impegno i a partire dalle massime sequenze ottenibili dagli impegni che lo precedono. Questo non mi sembra sia sempre corretto.
Nell’esempio che ti ho proposto per il quarto impegno crea una sequenza lunga tre sia col primo e secondo impegno ma con dataconclusione pari a 2+7+5=14 che con il primo ed il terzo e dataconclusione pari 2+5+5=12. Questa seconda scelta è preferibile alla prima in quanto permetterà di accettare il quinto impegno ma il tuo programma utilizza solo la primascelta e con dataconclusione=14 del quarto impegno il quinto non può essere utilizzato ed ecco dove sbaglia.

4

Ho controllato ed effettivamente con il tuo esempio sbagliava. Avevo invertito gli indici i e j nell’else if. Ora quella riga è corretta (o almeno credo) con dataConclusione[j] = dataConclusione[i] + durata[j];

Solo che provando il tuo esempio e anche quello proposto nel testo del problema, i risultati sono giusti, ma se poi sottopongo il programma mi restituisce 40/100 (addirittura piĂą baso di prima).

Purtroppo in questi casi non so mai che fare visto che non esiste un posto dove posso trovare piĂą esempi con le soluzioni corrette

5

Forse non ho capito bene la modifica che hai apportato: ora il codice è diventato?

else if (soluzioni[i] + 1 == soluzioni[j] && dataConclusione[j] > dataConclusione[i])
                        dataConclusione[j] = dataConclusione[i] + durata[j];

Perchè messo sotto debug mi continua a dare 3 invece di 4 per l’esempio che ti avevo inviato ed il problema continua ad essere quello che ti ho segnalato, quando andiamo ad esaminare l’impegno n.3
per i=2 abbiamo soluzioni[2]=3 e dataConclusione[2]=14 mentre dovrebbe esistere anche la possibilità (migliore): soluzioni[2]=2 e dataConclusione[2]=7 che permetterebbe di accettare in sequenza sia l’impegno 3 soluzioni[3]=3 e dataConclusione[2]=12 che l’impegno 4 con soluzioni[4]=4 e dataConclusione[4]=15 . Temo che il tuo programma non gestisca tutte le situazioni che si possono presentare ma solo quelle che sembrano essere le migliori perchè danno nell’immediato la soluzione maggiore: per N=3 soluzioni[2]=3 e dataConclusione[2]=14 è senz’altro la migliore ma non è a partire da questa che si otterrà la migliore soluzione per N=5.

6

Esatto, quella è la modifica che ho apportato. Io però se lo eseguo mi restituisce 4 e il caso proposta da te si risolve correttamente, infatti gli array alla fine risultano:
dataConclusione: [2, 9, 7, 12, 15]
soluzioni: [1, 2, 2, 3, 4]

Per sicurezza ti lascio di nuovo il codice, ma l’ho confrontato e quella è l’unica modifica che ho fatto e che mi fa venire il tuo caso.

int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

int N;
cin >> N;
vector<int> durata(N), scadenza(N);

for(int i = 0; i < N; i++)
    cin >> durata[i] >> scadenza[i];

vector<int> soluzioni(N), dataConclusione(N);

soluzioni[0] = 1;
dataConclusione[0] = durata[0];

for(int j = 1; j < N; j++) {
    soluzioni[j] = 1;
    for(int i = 0; i < j; i++) {
        if(scadenza[j] - durata[j] >= dataConclusione[i]) {
            if(soluzioni[i] + 1 > soluzioni[j]) {
                soluzioni[j] = soluzioni[i] + 1;
                dataConclusione[j] = dataConclusione[i] + durata[j];
            } else if(soluzioni[i] + 1 == soluzioni[j] && dataConclusione[j] > dataConclusione[i])
                dataConclusione[j] = dataConclusione[i] + durata[j];
        }
    }
}

cout << *max_element(soluzioni.begin(), soluzioni.end());

return 0;}
7

Ho riprovato a copia incollare il tuo nuovo codice ma non mi cambia niente?!
Tra l’altro con l’esempio che ho proposto in quel else if sotto debug il programma non entra mai
ed ottengo
dataConclusione: [2, 9, 14, 14, 12]
soluzioni: [1, 2, 3, 3, 3]

inoltre
else if(soluzioni[i] + 1 == soluzioni[j] && dataConclusione[j] > dataConclusione[i])

a dataConclusione[j] è sempre già stato assegnato un valore quando eseguiamo l’if() ?

Non so che altro dire comunque se ti interessa vedere un modo per risolvere questo problema con la programmazione dinamica ti posso inviare il mio anche se esiste un metodo che ritengo sia piĂą furbo!

8

Non ho la più pallida idea del perché a te continui a restituire 3 invece di 4. Ho provato anche ad usare un compilatore online, ma a me restituisce sempre 4.

dataConclusione è un vettore inizializzato a 0. Quella condizione serve soltanto quando il programma trova che è possibile fare lo stesso numero di missioni già calcolato, ma finendo prima (che è per forza meglio) e quindi assegna soltanto la nuova data di fine di una missione. Esempio:

Quando j = 3 e i = 2 abbiamo che gli array dataConclusione e soluzioni risultano:

dataConclusione: [2, 9, 7, 14, 0]
soluzioni: [1, 2, 2, 3, 0]

Questo soluzioni[j] = 3 si può ottenere in due modi visto che può decidere di fare le missioni 0, 1, 3 o le missioni 0, 2, 3. Quest’ultimo però è il caso migliore visto che se si decidesse di prendere le missioni 0, 1, 3 si finirebbe il giorno 14 (2 + 7 + 5), e quindi non si potrebbe prendere l’ultima missione.

Mettendo quell’else if il programma risolve questo problema, infatti:
soluzioni[2] + 1 == soluzioni[3] && dataConclusione[3] > dataConclusione[2]

Sostituendo i valori (e ricordandoci che j = 3 e i = 2):
2 + 1 == 3 && 14 > 7 → TRUE

Quindi:
dataConclusione[3] = dataConclusione[2] + durata[3];

Sostituendo i valori risulta:
dataConclusione[3] = 7 + 5 = 12

In conclusione gli array risultano:
dataConclusione: [2, 9, 7, 12, 0]
soluzioni: [1, 2, 2, 3, 0]

Purtroppo però non ho ancora capito cosa sbaglia il mio programma :thinking:

9

Dovrei aver trovato l’inghippo prova con l’esempio sotto:

ho provato a sviluppare una soluzione in programmazione dinamica bottom up e va ma è abbastanza diversa da quella che proponi.

1 Mi Piace
10

Ho finalmente capito dove sbagliava il mio programma.
Grazie mille!

11 
for (i=0;i<n;i++)
for(j=scadenza[i]-durata[i];j>=0;j--)
if(soluzioni[j]+1>soluzioni[j+durata[i]]
  soluzioni[j+durata[i]]=s[j]+1;