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

Sign in to follow this  
Aqua Costa

ONI'2008 - O Carteiro Paulo [RESOLVIDO]

Recommended Posts

Aqua Costa

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

Share this post


Link to post
Share on other sites
pmg

Experimenta com 8 sacos, 100 Kg.

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


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
pmg

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.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
Aqua Costa

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º  :)

Share this post


Link to post
Share on other sites
pmg

4 sacos, 100 Kg

60 30 39 3


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
pcaldeira

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.

Share this post


Link to post
Share on other sites
Aqua Costa

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?

Share this post


Link to post
Share on other sites
pcaldeira

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.

Share this post


Link to post
Share on other sites
Aqua Costa

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...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.