• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Aqua Costa

ONI'2008 - O Carteiro Paulo [RESOLVIDO]

12 mensagens neste tópico

Código a meu ver sem erros

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cmath>

/* Problema de preparação para ONI'2009
   URL do Problema: http://www.dcc.fc.up.pt/oni/problemas/2008/qualificacao/probC.html
   
   Data de Incio: 19 Janeiro 2009 16:51
   Data de Conclusão: 19 Janeiro 2009 21:13
       
   Tiago José Vieira Pires Costa
*/

using namespace std;

class CENTRAL_CORREIOS
{
      private:
             int nSacos;     //número de sacos
             int maxCarga;   // carga máxima que o carteiro consegue transportar
             int pesos[500]; // peso da cada saco
      public:
             int pMaximo;    //peso máximo que o carteiro pode transportar
             int ENTRADA(void);
     int ORDENA(void);
             int CALCULO(void);
             
} CC;


// Funão de entrada de dados
int CENTRAL_CORREIOS::ENTRADA(void)
{
    int I;
   
    cout << "Insira o numero de sacos [espaço] e a carga maxima da carrinha:" << endl;
    cin >> nSacos >> maxCarga;
   
    cout << endl << endl << "Insira o peso de cada sacos:" << endl;
    for (I = 0; I <= (nSacos - 1); I++)
    {
        cin >> pesos[i];
    };
    return 0;
};

int CENTRAL_CORREIOS::ORDENA(void)
{
     int i, j, flag = 1;
    int temp;
    for(i = 1; (i <= nSacos) && flag; i++)
    {
          flag = 0;
          for (j=0; j < (nSacos -1); j++)
          {
               if (pesos[j+1] > pesos[j])
               { 
                    temp = pesos[j];
                    pesos[j] = pesos[j+1];
                    pesos[j+1] = temp;
                    flag = 1;
               }
          }
     }
     return 0;
}

//Calcula o peso máximo possivél que o carteiro consegue transportar sem separar nenhum dos sacos
int CENTRAL_CORREIOS::CALCULO(void)
{
    int Z, X, total = 0, ntotal = 0;
   
    for (Z = 0; Z <= nSacos - 1; Z++)
    {
        ntotal = 0;
        ntotal = pesos[Z];
       
        for (X = Z + 1; X <= nSacos - 1; X++)
        {
            if (Z != X)
            {
                  ntotal += pesos[X];
                  if (ntotal > maxCarga)
                  {
                     ntotal -= pesos[X];
                  }
            }
        }
        if (ntotal > total && ntotal <= maxCarga)
        {
             total = ntotal;
		 pMaximo = total;
        }
    }
    return 0;
};

int main()
{
    CC.ENTRADA();
CC.ORDENA();
    CC.CALCULO();
   
    cout << endl << CC.pMaximo << endl << endl;
   
    system("PAUSE");
    return EXIT_SUCCESS;
}

Caso saibam alguma forma para melhorar o código digam :)

Penso que este tópico pode ser movido para Armazém de Código

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Experimenta com 8 sacos, 100 Kg.

Peso dos sacos: 60 30 30 33 34 1 1 1

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

realmente não funciona... sabes onde está o erro?

O erro está no algoritmo :)

Tu só apanhas no máximo dois sacos para transportar.

Além disso, as tuas contas

[pre]ntotal += CC.pesos[X];

ntotal -= CC.pesos[X];[/pre]

não batem certo uma com outra. Fazes mais vezes a soma que a subtracção.

Não pensei no algoritmo que resolve o problema, mas não é tão simples como o teu código pretende.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Este é um típico problema de knapsack! :) (Oxalá eu soubesse aquando das ONI :) )

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O erro está no algoritmo :)

Tu só apanhas no máximo dois sacos para transportar.

Além disso, as tuas contas

[pre]ntotal += CC.pesos[X];

ntotal -= CC.pesos[X];[/pre]

não batem certo uma com outra. Fazes mais vezes a soma que a subtracção.

Não pensei no algoritmo que resolve o problema, mas não é tão simples como o teu código pretende.

neste caso realmente só apanhava no máximo dois sacos, por isso examinei de novo a lógica que estava a usar e fiz alguma correções e agora já funciona com os teus valores (sem usar o knapsack :)) mas continua a não funcionar totalmente :)

#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cmath>

/* Problema de preparação para ONI'2009
   URL do Problema: http://www.dcc.fc.up.pt/oni/problemas/2008/qualificacao/probC.html
   
   Data de Incio: 19 Janeiro 2009 16:51
   Data de Conclusão: 19 Janeiro 2009 21:13
        
   Tiago José Vieira Pires Costa
*/

using namespace std;

class CENTRAL_CORREIOS
{
      private:
             int nSacos;     //número de sacos
             int maxCarga;   // carga máxima que o carteiro consegue transportar
             int pesos[500]; // peso da cada saco
      public:
             int pMaximo;    //peso máximo que o carteiro pode transportar
             int ENTRADA(void);
             int CALCULO(void);
             
} CC;


// Funão de entrada de dados
int CENTRAL_CORREIOS::ENTRADA(void)
{
    int I;
    
    cout << "Insira o numero de sacos [espaço] e a carga maxima da carrinha:" << endl;
    cin >> nSacos >> maxCarga;
    
    cout << endl << endl << "Insira o peso de cada sacos:" << endl;
    for (I = 0; I <= (nSacos - 1); I++)
    {
        cin >> pesos[i];
    };
    return 0;
};


//Calcula o peso máximo possivél que o carteiro consegue transportar sem separar nenhum dos sacos
int CENTRAL_CORREIOS::CALCULO(void)
{
    int Z, X, total = 0, ntotal = 0;
    int *maxp = new int[500];
    
    for (Z = 0; Z <= nSacos - 1; Z++)
    {
        ntotal = 0;
        ntotal = pesos[Z];
        
        for (X = Z + 1; X <= nSacos - 1; X++)
        {
            if (Z != X)
            {
                  ntotal += pesos[X];
                  if (ntotal > maxCarga)
                  {
                     ntotal -= pesos[X];
                  }
            }
        }
        if (ntotal > total && ntotal <= maxCarga)
        {
             total = ntotal;
             pMaximo = total;
        }
    }
    return 0;
};

int main()
{
    CC.ENTRADA();
    CC.CALCULO();
    
    cout << endl << CC.pMaximo << endl << endl;
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

pmg se quiseres volta a testar para ver se encontras mais algum erro e obrigado por teres encontrado o 1º  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema é mesmo um 0-1 knapsack típico. Resolve-se com programação dinâmica, ou seja, reaproveitando soluções para casos mais pequenos em vez de repetir cálculos. A página da wikipedia deve estar suficientemente clara (não a li detalhadamente), mas repara que o pseudo-código que lá está para a solução com DP corre em n*W a nível de memória. Se fizeres as contas, vês que não passa no limite de memória das ONI, ou seja, tens que modificá-lo de modo a correr em W. Só estou a alertar para isto porque quando resolvi esse problema, uma das minhas submissões tinha um código parecido com esse (da wikipédia) e tive que optimizar (a nível de espaço) para que passasse todos os testes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema é mesmo um 0-1 knapsack típico. Resolve-se com programação dinâmica, ou seja, reaproveitando soluções para casos mais pequenos em vez de repetir cálculos. A página da wikipedia deve estar suficientemente clara (não a li detalhadamente), mas repara que o pseudo-código que lá está para a solução com DP corre em n*W a nível de memória. Se fizeres as contas, vês que não passa no limite de memória das ONI, ou seja, tens que modificá-lo de modo a correr em W. Só estou a alertar para isto porque quando resolvi esse problema, uma das minhas submissões tinha um código parecido com esse (da wikipédia) e tive que optimizar (a nível de espaço) para que passasse todos os testes.

ainda não li o artigo da wikipedia e talvez por isso não percebi o que significa isso do W... podes explicar?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ainda não li o artigo da wikipedia e talvez por isso não percebi o que significa isso do W... podes explicar?

O W que referi ali é o peso máximo. Com o código que está na página da wikipédia, usas memória proporcional ao número de sacos * o peso máximo que o carteiro pode levar. No pior caso, ou seja, quando o número de sacos e o peso tomam os valores máximos, n*W excede o limite de memória.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

após estar algum tempo parado, resolvi voltar a pegar neste problema e descobri que se tiver os pesos por ordem não ocorrem erros...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora