vector<Cidade> Knapsackproblem(Viagem v, Path p, int tempoMax){

	vector<Cidade> res;

	p.getGraph().setA(new int *[v.getCidades().size()+1]);

	for(size_t i=0; i < v.getCidades().size()+1; ++i){
		p.getGraph().getA()[i] = new int [tempoMax+1];
	}

	for(size_t i=0; i < v.getCidades().size()+1; ++i){
		for(size_t j=0; j < tempoMax +1; ++j){
			p.getGraph().getA()[i][j] = 0;
		}
	}

	int iMax = 0;
	int jMax = 0;
	vector<pair<int,int> > classificacoes;

	for(size_t i =0; i < v.getCidades().size()+1; ++i){
		for(size_t j=0; j < tempoMax+1; ++j){
			if(i==0){
				p.getGraph().getA()[i][j] = 0;
			}
			else{
				if(p.getGraph().getVertexSet().at(i-1)->getInfo().getTempo() <= j){
					int dif_tempos = j - p.getGraph().getVertexSet().at(i-1)->getInfo().getTempo();
					if( p.getGraph().getVertexSet().at(i-1)->getInfo().getClassificacao() + p.getGraph().getA()[i-1][dif_tempos] > p.getGraph().getA()[i-1][j]){
						p.getGraph().getA()[i][j] = p.getGraph().getVertexSet().at(i-1)->getInfo().getClassificacao() + p.getGraph().getA()[i-1][dif_tempos];
					}
					else {
						p.getGraph().getA()[i][j] = p.getGraph().getA()[i-1][j];
					}
				}
				else
				{
					p.getGraph().getA()[i][j] = p.getGraph().getA()[i-1][j];
				}
			}
			pair<int,int> p;
			p.first = i;
			p.second = j;
			classificacoes.push_back(p);
		}
	}

	//encontrar o maximo das classificações

	sort(classificacoes.begin(), classificacoes.end());

	iMax = classificacoes.at(classificacoes.size() -1).first;
	jMax = classificacoes.at(classificacoes.size() -1).second;


	//encontrar as cidades a serem usadas.

	size_t j=jMax;
	size_t i=iMax;

	while(i>0 && j>0){
		if(p.getGraph().getA()[i][j] != p.getGraph().getA()[i-1][j]){
			res.push_back(p.getGraph().getVertexSet().at(i-1)->getInfo());
			j -= p.getGraph().getVertexSet().at(i-1)->getInfo().getTempo();
			i--;
		}
		else  i--;
	}


	return res;

}