Missioni segrete 20/100

Aiuto
1

Ecco qui:
Il codice prende come prima missione quella che ha somma fra durata e scadenza minima;
Va avanti e prende la missione con la durata minima e per la quale la somma dei giorni fino ad ora è minore della scadenza;
Se invece ci sono più durate uguali, prendo la missione con la scadenza minore;
(Errore di battitura: nel programma riportato d è la scadenza e s la durata)

#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
const int MAX=100;
int d[MAX],s[MAX],v[MAX];
void solve(int n,int dim,int& cont,int somm);
int main()
{
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   int n;
   cin>>n;

   for(int i=0;i<n;i++)
   {
   	cin>>s[i]>>d[i];
   }
   
   int min=INT_MAX,cont=0,dim=0,somm,ind;
   for(int i=0;i<n;i++)
   {
   	if(d[i]+s[i]<min)
   	{
   		min=d[i]+s[i];
   		ind=i;
   	}
   }
   v[0]=ind;
   dim++;
   cont++;
   somm=s[ind];
   solve(n,dim,cont,somm);
   cout<<cont;
}
void solve(int n,int dim,int& cont,int somm)
{
   bool contr,trov=false;
   int mind=INT_MAX,mins=INT_MAX,ind;
   for(int i=0;i<n;i++)
   {
   	contr=false;
   	for(int j=0;j<dim and contr==false;j++)
   	{
   		if(v[j]==i) contr=true;
   		else contr=false;
   	}
   	if(contr==false)
   	{
   		if(s[i]<mins and somm+s[i]<=d[i])
   		{
   			mins=s[i];
   			mind=d[i];
   			ind=i;
   			trov=true;
   		}
   		else if(s[i]==mins)
   		{
   			if(d[i]<mind)
   			{
   				mins=s[i];
   				mind=d[i];
   				ind=i;
   				trov=true;
   			}
   		}
   	}
   }
   if(trov==true)
   {
   v[dim]=ind;
   somm+=mins;
   dim++;
   cont++;
   solve(n,dim,cont,somm);}
}
2 Mi Piace
2

Da come l’hai descritto se l’ultima missione è la seconda più breve allora ne svolgi al più 2, ti ricordo che devi mantenere l’ordine cronologico con le missioni.

2 Mi Piace
3

Ti sbagli. Se l’input d’esempio fosse
3 5, 3 9, 4 8, 6 12,
Il programma prende come prima missione 3 5 perché è quella con somma fra durata e scadenza minima, poi prende 3 9 perché è quella con durata più piccola fra le restanti e 3+3=6<9, 4 8 non può prenderlo perché 3+3+4=10>8 quindi prende 6 12.
3 missioni

2 Mi Piace
4

Quindi cerchi sempre quella che finirebbe prima tra le disponibili giusto?

2 Mi Piace
5

Giusto, così ho maggiori possibilità di rientrare nei limiti di scadenza

2 Mi Piace
6

Non rischi di fare un prima una missione breve che potrai fare tra molto togliendoti la possibilità di fare una missione un po’ più lunga ma che puoi fare solo ora?

2 Mi Piace
7

Hai ragione…
Alla luce di quanto detto proverò più tardi a modificare il codice. Tu hai già qualche idea in mente?

2 Mi Piace
8

Onestamente non ricordavo la soluzione che avevo scritto in passato quindi l’ho risolto da 0.
Quello che ho notato è che le assunzioni sono veramente piccole, quindi puoi analizzare le missioni in ordine di scadenza(in questo modo per ogni missione che aggiungi utilizzi i primi d giorni liberi che hai) e per ogni missione decidere di compierla o meno, ovviamente nel caso in cui la sua durata + i giorni già usati superano la scadenza non puoi compierla.

Scrivendola in Top-Down puoi memorizzare il miglior valore ottenuto avendo utilizzato già g giorni all’iesima missione, ottenendo quindi al più 100*365 stati.

2 Mi Piace
9

Quindi potrebbe essere una soluzione valida prendere in ordine crescente le missioni in ordine di scadenza e considerarle se la somma dei giorni non supera la scadenza? Mi sembra troppo facile

2 Mi Piace
10

Quello non funziona, quello che funziona è provare ogni possibile combinazione andando in ordine di scadenza.

2 Mi Piace
11

Ok, ho modificato il programma: 70/100


#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
const int MAX=100;
int d[MAX],s[MAX],v[MAX],soluz[100*365];
int solve(int ind,int n,int dim,int passo,int ora,int max);
int main()
{
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   int n;
   cin>>n;
   for(int i=0;i<n;i++)
   	cin>>d[i]>>s[i];
   
   int max=-INT_MAX,caso,dim=0,passo=1,ora=0,mass=-INT_MAX;
   //PER OGNI MISSIONE LA FUNZIONE SOLVE RITORNA IL MASSIMO NUMERO DI MISSIONI CONSECUTIVE: STAMPIAMO IL MASSIMO NUMERO DI CASI 
   for(int i=0;i<n;i++)
   {
   	caso=solve(i,n,dim,passo,ora,mass);
   	if(caso>max)
   		max=caso;
   	//cout<<endl<<endl<<max<<endl<<endl;
   }
   cout<<max;
}
int solve(int ind,int n,int dim,int passo,int ora,int max)
{
   bool contr;
   int presi=0,somm=0;
   for(int i=ind;presi<n;)
   {
   	//CONTROLLO CHE NON SIA GIA' STATA CONSIDERATA LA MISSIONE
   	contr=false;
   	for(int j=0;j<dim and contr==false;j++)
   		if(v[j]==i) contr=true;
   		
   	if(contr==false)
   	{
   		presi++;
   		if(d[i]+ora<=s[i]) 
   		{
   			v[dim]=i;
   			dim++;
   			somm++;
   			ora+=d[i];
   		
   		}
   	}
   	if(i==n-1) i=-1;
   	 
   	if(i==ind and contr==false)	i+=passo;
   	else i++;
   	
   	if(i>=n) i=i-n;

   }
   for(int i=0;i<dim;i++)
   	v[i]=-1;

   
   if(passo<n-1)
   {
   	//cout<<"somm: "<<somm<<", max: "<<max<<endl;
   	if(somm>max) max=somm;
   	//cout<<"somm2: "<<somm<<", max2: "<<max<<endl<<endl;
   	somm=solve(ind,n,dim,passo+1,0,max);
   }
   else if(passo==n-1) 
   {
   	//cout<<"somm: "<<somm<<", max: "<<max<<endl;
   	if(somm>max) max=somm;
   	//cout<<"somm2: "<<somm<<", max2: "<<max<<endl<<endl;
   }
   //cout<<max<<endl;
   return max;
}

Ora dovrebbe considerare tutti i percorsi.
Il problema è che per alcuni input, come quello d’esempio, return max non ritorna effettivamente la somm massima

2 Mi Piace
12

Ti da wrong answer oppure TLE?

Preciso che potresti snellire molto il codice, soprattutto la funzione ricorsiva può essere qualcosa come (è una specie di pseudocidc):

int f(int pos, int giorno){
    if(pos==n) return 0;
    int res=f(pos+1,giorno); // non faccio questa missione 
    if(sta nella scadenza)
        res=max(res+f(pos+1,giorno+scadenza);
    return res;
}

Aggiungendo la memoizzazione.

E basta richiamarla con f(0,0), gli altri stati verranno richiamati automaticamente

2 Mi Piace
13

Mi da Output isn’t correct… non capisco dove sbaglio :face_with_raised_eyebrow:

1 Mi Piace
14

La mia idea per la prima parte è come quella proposta da @frakkiobello: andare in ordine di sequenza ed accettare tutte le missioni che non terminerebbero oltre la scadenza ma quando questo non è verificato, ovviamente non la posso aggiungere ma posso vedere se è possibile scambiarla con una già accettata ma di … il numero di impegni non aumenta ma in seguito avrò maggiori chance per accettarne altre.
Può servire un maxheap (priority_queue)

1 Mi Piace