Ir ao conteúdo
  • Cadastre-se
lucasprados

C++ Problema da Mochila C++

Recommended Posts

Meu professor me passou o problema da mochila para programar em C++, até ai tudo bem, entendo a lógica do problema perfeitamente. Porém ele pediu para fazer a leitura de arquivos externos com os valores e pesos de cada item, com isso não estou conseguindo desenvolver o algoritmo, se alguém puder por favor me ajudar.
Segue abaixo a parte que ele já entregou desenvolvida, tenho apenas que fazer a lógica, lendo o arquivo externo.

 

#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <bitset>
#include <time.h>
//#include "boost/dynamic_bitset.hpp"

using namespace std;

typedef struct{
  int n;                //total de itens
  int C;                //Capacidade da Mochila
  std::vector <double> v;         //valor dos itens
  std::vector <double> p;         //peso dos itens
  char *name;                       //
  time_t t_max;                     //tempo maximo de execucao
  int it_max;                       //numero maximo de iterações
} DAT; //armazena os dados lidos

typedef struct{
    double z;                   //custo total da solucao
    std::bitset<100> x;  //sinaliza quais itens estão presentes na solucao
} SOLUTION;

void leitura_dados(DAT &d);
void imprime_solucao(DAT d, SOLUTION s);
void help();
//funcao de ordenacao
void sort(std::vector<double> &cost,  std::vector<int> &R, int tam);

void help(){
  std::cout << std::endl << std::endl << "exec [data file] \n " << std::endl;
  exit(1);
}

void leitura_dados(DAT &d){     //prestar atencao no &, indicando que o elemento ou variavel pode ter algum valor modificado dentro dessa funcao
    //leitura do tempo
    std::cout << "Digite o tempo maximo de compilacao" << std::endl;
    std::cin >> d.t_max;

    std::cout << "Digite o numero maximo de iteracoes" << std::endl;
    std::cin >> d.it_max;
    //*/
    //leitura de dados
    //string nname = "tsp-d01.dat";
    string nname;
    std::cout << "Digite o nome da instacia: " << std::endl;
    std::cin >> nname;

    //convertendo string para char[]
    char *cname = new char[nname.length()+1];
    memcpy(cname, nname.c_str(), nname.length() + 1);
    d.name = cname;
    //fim conversao string para char

    //abertura do arquivo de dados
    ifstream arq(cname);
    if (!arq.is_open()) help();

    //leitura dos dados

    //total de itens
    arq >> d.n;
    std::cout << "\nn: " << d.n;

    //Capacidade da Mochila
    arq >> d.C;
    std::cout << "\nC: " << d.C;

    d.v = std::vector<double>(d.n+1, 0.0);
    d.p = std::vector<double>(d.n+1, 0.0);

    for (int j = 1; j <= d.n; j++){
        arq >> d.v[j];
        arq >> d.p[j];
        std::cout << "\nj: " << j << " v: " << d.v[j] << " - p: " << d.p[j];
    }
    std::cout << std::endl;
    arq.close();
}

void imprime_solucao(DAT d, SOLUTION s){
    std::cout << "\n-------------------------------------------\nIMPRESSAO DA SOLUCAO \nProblema: " << d.name << "\ncusto: " << s.z << "\ncomposicao: " << s.x << "\nx: ";
    for (int j = 1; j <= d.n; j++) if (s.x.test(j-1)) std::cout << j << " ";
    std::cout << "\n-------------------------------------------\n";
}

void sort(std::vector<double> &cost,  std::vector<int> &R, int tam){
    int i, j, imin, iaux;
    double daux;
    for (i = 1; i <= tam; i++){ // para todas as posições
        imin = i;
        for (j = (i+1); j <= tam; j++) if(cost[j] < cost[imin]) imin = j; //avalio o valor armazenado

        if (i != imin) {
            daux = cost;
            cost = cost[imin];
            cost[imin] = daux;

            iaux = R;
            R = R[imin];
            R[imin] = iaux;
        }
    }
}


int main()
{
    //leitura das informações do problema
    DAT d;
    leitura_dados(d);

    //heuristica

    //metaheuristica
}

 

Caso alguém me entregue o algoritmo pronto e funcionando, entrarei em contato e recompensarei

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×