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

Warrior

[5] Phidias - Nível elevado

29 mensagens neste tópico

No exemplo de input, uma das peças necessárias tinha dimensões 15x10, mas pela figura mostrada, não é cortado nenhum pedaço de mármore com essas dimensões. Isto significa que não temos de cortar pelo menos uma porção de mármore de cada um dos tamanhos recebidos no input?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Como dito no enunciado:

Ele pode fazer 0 ou mais placas de cada um dos tamanhos pretendidos. (é um monumento bastante grande)

Portanto não, não temos que cortar pelo menos um de cada tamanho.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ups. Escapou-me :D

A minha solução está em O( L * H * (L+H) ). Penso que passa no tempo (se fosse um concurso :D) tranquilamente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu tenho aqui num livro um exemplo parecido com este :) (Curiosidade: o livro é o Indrodução à Programação usando C da FCA) seria só adaptar ;).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu tenho aqui num livro um exemplo parecido com este :) (Curiosidade: o livro é o Indrodução à Programação usando C da FCA) seria só adaptar ;).

Em que página? Tenho aqui o livro e não me lembro de abordar estes temas, de todo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Começa na página 86, é o das calhas de aluminio :).

Já agora, o que achas do livro?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Começa na página 86, é o das calhas de aluminio :).

Já agora, o que achas do livro?

Sinceramente não li o livro, ganhei-o num concurso qualquer numa altura em que precisava de tudo menos um livro de Introdução ao C.. Pelo que vi de passagem parece-me fraco.

O problema em si é bastante diferente deste: repara que as calhas de alumínio só possuem uma dimensão enquanto que aqui tratamos de duas.

Por outro lado, não me parece que a solução apresentada seja a mais correcta uma vez que é usada uma solução greedy e o problema de multiple knapsack obriga a pesquisa exaustiva.. (ou seja, por vezes pode dar mais desperdícios do que o necessário)

Este problema 5 é um Desafio, e se ninguém o discutir ninguém o resolve.

Mostrem as conclusões que já tiraram e os pormenores que podem ajudar outros a resolver o problema..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mostrem as conclusões que já tiraram e os pormenores que podem ajudar outros a resolver o problema..

Se temos uma peça de mármore de dimensões  x*y para cortar e se as dimensões desta peça estiverem na lista de tamanhos necessitados, o desperdicio é 0. Senão temos de a cortar de forma a minimizar o desperdicio ...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A mim o que me parece fundamental para resolver o problema é esta particularidade:

Suponham que têm uma placa 10x10. Decidem cortá-la em duas 10x5.

Se acharmos o desperdício de uma das placas 10x5, o desperdício da segunda placa é exactamente o mesmo. Ou seja, quaisquer duas placas AxB terão sempre o mesmo desperdício, independentemente da posição.

Queria também realçar que a solução a este problema é bastante simples de implementar, só é preciso a ideia..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas!

A minha ideia para o problema é criar um tipo de dados que se chama 'node' contem ( x,y da placa principal, 'Pontos' [ ](1) , int espaço livre) ! Depois do tipo de dados estar criado , crio uma FIFO do tipo 'node' onde vou adicionar um 'node' que contem (placa principal , array vazio , x*y), ou seja vai ser a placa sem cortes!

Depois retiro o elemento da FIFO e vou pondo na FIFO novos elementos baseados nos cortes do elemento retirado!

E vou fazendo uma verificação aos elementos que retiro da FIFO, que é se é possível fazer mais cortes, se nao forem comparo o tamanho disponível com o o menor tamanho disponível encontrado ate a altura.

(1): pontos, vai ser outro tipo de dados que vai conter 2 pontos num plano x,y!

o array de pontos vai conter os cortes feitos na placa. 

Os pontos escolhidos para definir o corte são o mais a esquerda e acima possível, e o mais abaixo e á direita possível

Nao sei se esta esclarecedora a minha ideia :S

Isto é basicamente brute force:S 

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Brute force puro não passa no tempo.

O teu também é brute force, logo também não passaria, mas tem um problema extra: não garante a solução óptima.

Cortar simplesmente o mais à esquerda e acima possível não garante que vamos minimizar a área desperdiçada.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que podes começar pelo brute force e depois pensas em alguma forma de melhorar.

Na tua ideia não percebi como é que ao usar o fifo, calculas a resposta final. Esse array de pontos parece-me desnecessário porque, tal como o Warrior disse, tens de fazer mais do que 2 cortes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Brute force puro não passa no tempo.

O teu também é brute force, logo também não passaria, mas tem um problema extra: não garante a solução óptima.

Cortar simplesmente o mais à esquerda e acima possível não garante que vamos minimizar a área desperdiçada.

Pois também cheguei agora á conclusão que assim não daria o mínimo correcto :/  Vou pensar noutra solução :)

Acho que podes começar pelo brute force e depois pensas em alguma forma de melhorar.

Na tua ideia não percebi como é que ao usar o fifo, calculas a resposta final. Esse array de pontos parece-me desnecessário porque, tal como o Warrior disse, tens de fazer mais do que 2 cortes.

Nos desenhos que fiz parecia me ter lógica ,  agora já não :/ lool

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

hmm, já estive a pensar um bocado. Estava a pensar em algo com achar os múltiplos das placas, o problema é que como estou a imaginar agora só funcionaria para os casos em que a placa original seria toda aproveitada, ou seja, quando não houvesse sobras.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Já coloquei a minha solução com Programação Dinâmica, pode ser que ajude a compreender a ideia.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Solução com memoization colocada :)

No fundo é feito o brute-force, mas o truque é guardar os resultados calculados numa tabela (neste caso uma matriz) para não recalcular coisas. Basicamente este é o significado de Programação Dinâmica (continuo a achar o nome tão pomposo lol).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nem sabia o que era programação dinâmica :/

Na soluçao do Warrior estao duas coisas que desconheço por completo, podiam me  dizer o que faz o "continue;"

      e o " min=1<<30;"

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

o continue avança para a próxima iteração do ciclo, ignorando as instruções que estão a seguir.

As operações bit-a-bit são muito uteis. 1<<30 é um shift lógico à esquerda é o mesmo que fazer min = 230 (ou seja min = 1073741824 ), mas um shift é muito rápido e não existe operador para potência em C ou C++.

PS: Sei que em Java e C# estas operações existem e a sintaxe é a mesma.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É mesmo isso.

De qualquer modo já alterei o 1<<30 e coloquei i*j, uma vez que simplifica o código porque posso retirar o operador ternário mais abaixo..

Tudo passa por perceber que o desperdício da nossa placa LxC será o menor desperdício possível das somas Li x C + (L-Li) x C, L x Ci + L x (C - Ci) para todos os i válidos.

Se depois implementamos com programação dinâmica (ou seja, iterativamente) ou com memoization (recursivamente) já é uma questão de gosto.

Programação Dinâmica é só um nome complicado para uma técnica que se baseia em construirmos as nossas soluções partindo de soluções mais pequenas, como é o caso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

o continue avança para a próxima iteração do ciclo, ignorando as instruções que estão a seguir.

As operações bit-a-bit são muito uteis. 1<<30 é um shift lógico à esquerda é o mesmo que fazer min = 230 (ou seja min = 1073741824 ), mas um shift é muito rápido e não existe operador para potência em C ou C++.

PS: Sei que em Java e C# estas operações existem e a sintaxe é a mesma.

Sempre a aprender:D thanks

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Então e a tua solução não sai ? :)

A minha solução vai ter que ficar para o fim de semana;) se conseguir claro :)

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