Missioni segrete (missioni)

Aiuto
1

Stavo provando a risolvere questo problema con la programmazione dinamica top-down (la soluzione proposta sulla guida di Bugatti è in bottom-up). Essendo nuovo alla programmazione dinamica non so bene come strutturare il tutto e il codice che ho scritto dà solo 20/100.
Qualcuno mi può dire dove sbaglio?
Grazie.
Il codice è qui di seguito:

#include <stdio.h>
int N;

typedef struct mission{
  int scad;
  int dur;
}mission;

mission M[100];
int sol[366];

int max(int a, int b){
  if(a>b) return a;
  else return b;
}

int calc(int current, int g){
  if(current==N) return 0;
  if(sol[g]!=0) return sol[g];
  int prendo=0, no=0;
  if(M[current].scad>=g+M[current].dur){
    prendo = 1+calc(current+1, g+M[current].dur);
  }
  no = calc(current+1,g);
  int m = max(prendo,no);
  sol[g]=m;
  return m;
}

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

  int i;
  scanf("%d", &N);
  for(i=0; i<N; i++){
    scanf("%d %d", &M[i].dur, &M[i].scad);
  }

  printf("%d",calc(0,0));

  return 0;
}
2 Mi Piace
2

L’errore è l’array sol, che dovrebbe essere bidimensionale, infatti deve tener conto sia del giorno in cui sei sia delle missioni analizzate fino ad ora, altrimenti non consideri certi combinazioni delle missioni, in quanto hai già settato la sol per quel giorno, ma arrivandoci con altre missioni.

3 Mi Piace
3

ok, grazie mille, provo :+1::+1:

2 Mi Piace
4

Ok, 100/100 grazie mille :+1::+1:
Ne approfitto per chiederti un consiglio: a parte la guida di Bugatti, dove posso trovare indicazioni sulla programmazione dinamica? Perché con gli altri argomenti utili alle territoriali me la cavo abbastanza, sollo sulla dp ho delle serie difficoltà nella modellizzazione del problema…

2 Mi Piace
5

Purtroppo non esiste una guida completa che, quando studiata, ti da piene abilità.

Il consiglio è aprire la categoria dp su training.olinfo e partire da quelli più semplici, scervellarti a sufficienza e se proprio non trovi la soluzione ad un problema(cosa molto probabile nel processo di apprendimento) chiedi su forum.

Tieni in mente che l’obiettivo non è fare 100/100 ma capire la logica per poi applicarla in contesti simili, per esempio cerca di capire (magari trovando un esempio) quali casi non risolveva la soluzione che avevi proposto.

4 Mi Piace