Jump to content
Sign in to follow this  
xtrm0

ONI 2008 - C

Recommended Posts

xtrm0

Olá. Tentei resolver o problema do Carteiro Paulo :dontgetit: http://mooshak.dcc.fc.up.pt/~oni-treino/cgi-bin/execute/48789249057317735 , usando a informacão sobre knapsack que estava aqui: http://www.portugal-a-programar.org/forum/index.php/topic,37094 .

Cheguei a este código:

#include <iostream>
#define max(a, b)  (a > b) ? a : b
using namespace std;

int main() {
   int pesos[5001];
   int C, P;
   int maxi=0, i, j;
   int solved[5001][5001];
   cin >> C >> P;
   for (int x=0; x<P; x++) cin >> pesos[x];

   for (int x=0; x<P; x++) {
       solved[x][0]=0;
       solved[0][x]=0;
   }
   for (i=1; i<P; i++) {
       for (j=1; j<P; j++) {
           solved[i][j]=max(((solved[i-1][j-pesos[i]])+pesos[i]), (solved[i-1][j]));
           if (solved[i][j]<=C && solved[i][j]>maxi) maxi=solved[i][j];
       }
   }
   cout << maxi << endl;
}

Só que, para alem da array solved ser muito grande, nao tenho as soluções certas.Onde é que errei.


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

O knapsack não está bem. Tens de percorrer a capacidade da "mochila" e não fazer ciclos Saco*Saco, se é que me entendo. Explicar porquê já requeria um texto algo extenso, seria preferível tentares procurar na net.

Sobre a matriz solved ser grande, em primeiro lugar, devias declarar as variaveis grandes como variaveis globais, senão vais exceder a capacidade da stack.

Por outro lado, olha bem para o código, em cada passo do ciclo, precisas de ter sempre a matriz toda em memória?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

Neste problema experimentei gerar todas as permutações possíveis, através da função next_permutation(), e ir vendo o máximo mas dá Time Limit Exceeded (24).

A única solução será usando knapsack? Alguém sabe onde posso aprender isso?


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
xtrm0

Estive a pesquisar na net e fiz o seguinte knapsack, com base neste algoritmo 'guloso' 🤔 em java :

http://pt.wikipedia.org/wiki/Problema_da_mochila

Só que a partir dos 20 pontos tenho wrong answer. Porquê?

#include <iostream>
#define max(a, b)  (a > b) ? a : b
using namespace std;
   int pesos[5001];
   int C, P;
   int maxi=0, a;
   int solved[5001][5001];

void knapsack() {
   int W = C;
   int j = P;
   int* w = pesos;
   int* x = new int[W];

   while (j >= 1 && w[j] <= W) {
       x[j] = 1; //insere o item na mochila
       W = W - w[j]; //decrementa a capacidade
       j--; //decrementa itens
       /*cout << "Peso do item "<< j <<": " << w[j] << endl;
       cout << "Espaço disponivel: " << W << endl;*/


       //invariante
       if (j >= 1) {
           x[j] = W / w[j]; //avalia se o item cabe na mochila
           for (int k = j - 1; k < j && k > 0; k--) {
               x[k] = 0;//os espaços não preênchidos recebem 0
            }
        }
    }
   cout << (C-W+1) << endl;
}

void insort() {
   int i, j, chave;
   for (j=1; j<P; j++) {
       chave = pesos[j];
       i=j-1;
       while (i>=0 && pesos[i] > chave) {
           pesos[i+1]=pesos[i];
           i--;
       }
       pesos[i+1]=chave;
   }

   return;
}
   int main() {
   cin >> P >> C;
   for (int x=0; x<P; x++) cin >> pesos[x];
   insort();
   knapsack();
   return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

o post do xtrm ja tem um link com uma explicação do knapsack. mas é cedo demais para já estares a ver este tipo de problemas. vê antes a usaco, no modulo 1 tem uma secção onde se aprende DFS, BFS, etc (depois da secção farias o da nuvem de cinzas facilmente), entre outros problemas. Depois mais tarde, no módulo 2 tem a explicação de programação dinâmica e alguns problemas, entre os quais o knapsack.

seguir essa ordem é muito melhor do que tentar andar a saltar tanto.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
skiller10

sendo assim vou continuar o USACO, vou hoje começar a secção 1.2 :D


"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share this post


Link to post
Share on other sites
mogers

Só que a partir dos 20 pontos tenho wrong answer. Porquê?

Foi proposto por George Dantzig, em 1957, um algoritmo de aproximação de greedy

É um algoritmo de aproximação, ou seja, nem sempre dá a resposta correcta (daí o WA). Volta ao teu código anterior, não está longe da solução.

PS: a usaco explica o que são algoritmos gulosos na secção 1.3 :D


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

E o primeiro exemplo que aparece naquele site também é greedy ou não?

Edit. Não me tinha aprecebido que greedy significava guloso :wallbash: .


<Signature goes here>

Share this post


Link to post
Share on other sites
Localhost

Penso que num caso que dão no enunciado demonstra logo que não podes utilizar um greedy algorithm neste problema..


here since 2009

Share this post


Link to post
Share on other sites
xtrm0

Já consegui fazer o knapsack :cheesygrin: .

Tive MLE 😡 .

Como é que faço para apagar a parte da matriz que não preciso?

#include <iostream>
#define max(a, b)  (a > b) ? a : b
using namespace std;
   int pesos[5001];
   int C, P;
   int maxi=0;
   int knap[5001][5001];


   int knapsack01() {
      // initial row  - solutions to the subproblems with no items selected
      for (int i = 0; i < C; i++)
          knap[0][i] = 0;
      // process one item at a time for each weight
      for (int k = 1; k <= P; k++)
          for (int y = 1; y <= C; y++)
               if (y < pesos[k-1])
                   knap[k][y-1] = knap[k-1][y-1];
               else
                   if (y > pesos[k-1])
                           knap[k][y-1] = max(knap[k-1][y-1], knap[k-1][y-1-pesos[k-1]] + pesos[k-1]);
                   else
                           knap[k][y-1] = max(knap[k-1][y-1], pesos[k-1]);
      cout << knap[P][C-1] << endl;
      return 0;
   }



   int main() {
   cin >> P >> C;
   for (int x=0; x<P; x++) cin >> pesos[x];
   knapsack01();
   return 0;
}


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

A resposta está mesmo à tua frente :D

Mantenho o que disse:

olha bem para o código, em cada passo do ciclo, precisas de ter sempre a matriz toda em memória?

Mais do que isto é dar mesmo a solução.

PS: a matríz não é 5000x5000. Seria 5000x10000 ou seja nº de sacos * capacidade


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
xtrm0

Obrigado. Percebi. Era só preciso ter uma array [2][10001].


<Signature goes here>

Share this post


Link to post
Share on other sites
mogers

Obrigado. Percebi. Era só preciso ter uma array [2][10001].

boa :)

deixo o exercício de perceberes como e porque é que a minha solução funciona:

edit: codigo removido


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

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  

×
×
  • Create New...

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.