Ir para o conteúdo
Warrior

[5] Phidias - Nível elevado

Mensagens Recomendadas

mogers    14
mogers

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?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Sag    0
Sag

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 

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Sag    0
Sag

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Betovsky    2
Betovsky

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Sag    0
Sag

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;"

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
mogers

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Warrior    68
Warrior

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Sag    0
Sag

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

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


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade