Problema Luiss laurea

Aiuto
1

Ciao a tutti, è la prima volta che scrivo su questo forum!
Ho provato a risolvere il problema laurea della gara Luiss ma ho ottenuto solamente 60/100:

18
181176×1402 110 KB

Non riesco a capire come fare per raggiungere 100/100, anche perché da questo CMS non posso vedere gli input dei testcases. Il codice che ho usato è:

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct Mezzo {
	int posti, numero, prezzo;
};

int main(){
	ifstream in("input.txt");
	ofstream out("output.txt");
	
	int N, totmezzi = 0;
	
	in >> N; //persone n.
	
	Mezzo mezzi[4];
	vector <int> prezzi;
	
	mezzi[0].posti = 2;
	mezzi[1].posti = 4;
	mezzi[2].posti = 5;
	mezzi[3].posti = 7;
	
	for(int i=0; i<4; i++){
		in >> mezzi[i].numero >> mezzi[i].prezzo;
		totmezzi += mezzi[i].numero;
	}
	
	for(int a=0; a<=mezzi[0].numero; a++)
		for(int b=0; b<=mezzi[1].numero; b++)
			for(int c=0; c<=mezzi[2].numero; c++)
				for(int d=0; d<=mezzi[3].numero; d++){
					int persone = a*mezzi[a].posti + b*mezzi[b].posti + c*mezzi[c].posti + d*mezzi[d].posti;
					if(persone >= N){
						int costo = a*mezzi[a].prezzo + b*mezzi[b].prezzo + c*mezzi[c].prezzo + d*mezzi[d].prezzo;
						prezzi.push_back(costo);
					}
				}
	
	sort(prezzi.begin(), prezzi.end());
	out << prezzi[0];
}

Consigli? Grazie!

1 Mi Piace
2

Prova a svolgerlo con la backtracking, è molto più semplice ed intuitivo

5

Ciao,
l’errore è in queste due righe:

int persone = amezzi[a].posti + bmezzi[b].posti + cmezzi[c].posti + dmezzi[d].posti;

int costo = amezzi[a].prezzo + bmezzi[b].prezzo + cmezzi[c].prezzo + dmezzi[d].prezzo;

dovrebbero essere:

int persone = amezzi[0].posti + bmezzi[1].posti + cmezzi[2].posti + dmezzi[3].posti;

int costo = amezzi[0].prezzo + bmezzi[1].prezzo + cmezzi[2].prezzo + dmezzi[3].prezzo;

ho inviato il tuo codice con questa correzione e da 100/100.

2 Mi Piace
6

Grazie mille!
@oleg.ivashkiv cosa intendi con backtracking? Ho cercato su internet ma non sono riuscito a capire bene

7

Prova a dare un’occhiata qui ,molto semplicemente provi tutti i tentativi possibili, cercando la soluzione migliore.
Se la implementi ricorsivamente è molto più semplice, in generale come approccio, soprattutto se non ottimizzato, è abbastanza lento ma qui le assunzioni sono molto permissive.

Fabio.

1 Mi Piace