Olá professor,
O enunciado do execício 11.1 diz que temos que montar um programa. Qual tipo de entrada e saída devemos admitir? Podemos seguir as do problema original que esta em http://online-judge.uva.es/p/v102/10261.html ?
Grato,
O exercício da tarefa 11 é mais complicado que os anteriores porque você deve inventar os detalhes do enunciado.
Não é necessário usar o nível de detalhe do Programming Challenges, pois você não precisa escrever um programa completo: basta escrever um algoritmo, na notação CLR. (É bom também provar que o seu algoritmo está correto.)
Não é necessário usar o nível de detalhe do Programming Challenges, pois você não precisa escrever um programa completo: basta escrever um algoritmo, na notação CLR. (É bom também provar que o seu algoritmo está correto.)
Professor, eu tenho uma dúvida sobre o enunciado da tarefa 11:
Na tarefa 11, é dito que "durante o embarque, o operador da balsa estima o comprimento do próximo carro e dirige esse carro para uma das duas pistas."
A frase acima implica que o operador só tem o conhecimento do comprimento do próximo carro, à lá "Tetris", e não dos comprimentos dos carros de toda a fila.
Já no Programming Challenges, o operador inspeciona toda a fila: "Each car in the queue has a different length, which the operator estimates by inspecting the queue".
Resumindo, na Tarefa 11 o operador conhece os comprimentos de todos os carros da fila, ou somente do próximo carro a embarcar?
Na tarefa 11, é dito que "durante o embarque, o operador da balsa estima o comprimento do próximo carro e dirige esse carro para uma das duas pistas."
A frase acima implica que o operador só tem o conhecimento do comprimento do próximo carro, à lá "Tetris", e não dos comprimentos dos carros de toda a fila.
Já no Programming Challenges, o operador inspeciona toda a fila: "Each car in the queue has a different length, which the operator estimates by inspecting the queue".
Resumindo, na Tarefa 11 o operador conhece os comprimentos de todos os carros da fila, ou somente do próximo carro a embarcar?
Acho que nao tem diferenca no algoritmo pois voce nao pode deixar carros de lado. Tem que colocar todos que couberem na ordem que forem aparecendo.
Acho que faz diferença, sim. Afinal, se você não contar com a informação a priori de todos os comprimentos, não há otimização combinatória a ser aplicada, mas sim uma estratégia onde sempre seria vantajoso colocar o automóvel no lado mais vazio da balsa (imagine um Tetris com apenas duas colunas, e somente peças "I", de comprimentos diferentes).
Eu tbm pensei isso no comeco, mas tome este caso:
Comprimento da balsa: 10
Comprimento dos carros: 1, 3, 5, 9, 1
Suponha que vc veja so o primeiro numero da fila como no enunciado, logo:
Chegou um carro com tamanho 1 e vc pode coloca-lo em ambos os lados. Logo
esquerda: 10 direita: 9
Chegou o carro com tamanho 3 e, pela sua estratégia vc colocaria no lado mais vazio, logo:
esquerda: 7 direita: 9
Chegou o carro com tamanho 5 e, pela sua estrategia vc colocaria no lado mais vazio, logo:
esquerda: 7 direita: 4
Chegou o carro com tamanho 9. Ele nao cabe na balsa, logo a resposta seria 3 o que esta incorreto, pois da para conseguir colocar mais carros.
O problema de saber os tamanhos ou nao, nao faz diferenca pq vc nao pode "pular" carros, logo da no mesmo. Repare que, so mudando a estratégia, da para achar a resposta correta sem precisar conhecer a lista toda. Ex:
Carro de tamanho 1:
esquerda: 10 direita: 9
Chegou o carro com tamanho 3:
esquerda: 10 direita: 6
Chegou o carro com tamanho 5:
esquerda: 10 direita: 1
Chegou o carro com tamanho 9:
esquerda: 1 direita: 1
Chegou o carro com tamanho 1:
esquerda: 0 direita: 1
Veja que agora eu consegui colocar todos. O que eu concordo e que, a quantidade de carros pode ser necessaria para escrever o algoritmo mas a lista em si nao.
Comprimento da balsa: 10
Comprimento dos carros: 1, 3, 5, 9, 1
Suponha que vc veja so o primeiro numero da fila como no enunciado, logo:
Chegou um carro com tamanho 1 e vc pode coloca-lo em ambos os lados. Logo
esquerda: 10 direita: 9
Chegou o carro com tamanho 3 e, pela sua estratégia vc colocaria no lado mais vazio, logo:
esquerda: 7 direita: 9
Chegou o carro com tamanho 5 e, pela sua estrategia vc colocaria no lado mais vazio, logo:
esquerda: 7 direita: 4
Chegou o carro com tamanho 9. Ele nao cabe na balsa, logo a resposta seria 3 o que esta incorreto, pois da para conseguir colocar mais carros.
O problema de saber os tamanhos ou nao, nao faz diferenca pq vc nao pode "pular" carros, logo da no mesmo. Repare que, so mudando a estratégia, da para achar a resposta correta sem precisar conhecer a lista toda. Ex:
Carro de tamanho 1:
esquerda: 10 direita: 9
Chegou o carro com tamanho 3:
esquerda: 10 direita: 6
Chegou o carro com tamanho 5:
esquerda: 10 direita: 1
Chegou o carro com tamanho 9:
esquerda: 1 direita: 1
Chegou o carro com tamanho 1:
esquerda: 0 direita: 1
Veja que agora eu consegui colocar todos. O que eu concordo e que, a quantidade de carros pode ser necessaria para escrever o algoritmo mas a lista em si nao.
Mas Thadeu, sem perceber você afirmou que, para efeitos de otimização, conhecer a lista é importante! De outra forma, como seu algoritmo "adivinharia" que é necessário guardar espaço em um dos lados, pois um veículo de tamanho 9 está por vir? 
Outro exemplo: uma balsa de tamanho 12, com carros vindo, na sequência: 3, 4, 3, 4, 3, 4, 3. Se for adotada a estratégia de seu último exemplo ("encher" primeiro um dos lados), o número de carros não será ótimo.
O fato de não pular carros é sim importante, você tem razão. Porém, ele é uma restrição adicional ao seu problema de otimização.
Outro exemplo: uma balsa de tamanho 12, com carros vindo, na sequência: 3, 4, 3, 4, 3, 4, 3. Se for adotada a estratégia de seu último exemplo ("encher" primeiro um dos lados), o número de carros não será ótimo.
O fato de não pular carros é sim importante, você tem razão. Porém, ele é uma restrição adicional ao seu problema de otimização.
Oi Marcelo,
No caminho da solucao eu vi que eh importante sim pois da para "chutar" ateh qual carro cabera e reduzir o espaco de busca.
Acho que isso teremos pois a assinatura do algoritmo pode exigir um array A com os carros e n, a quantidade de elementos. Certo?
No caminho da solucao eu vi que eh importante sim
Acho que isso teremos pois a assinatura do algoritmo pode exigir um array A com os carros e n, a quantidade de elementos. Certo?
Acho q se vc considerar apenas o primeiro carro da fila e o tamanho restante da fila vc terá um problema de solução trivial (acho q n tem como fugir muito disso)!!
O que o algoritmo da mochila ajuda é justamente se o operador inspeciona a fila e estima como ficarão os carros mesmo antes de embarcá-los!!!
Ou seja quais comprimentos w1, w2, w3, w4, ... serão distribuídos para maximizar W1 e W2???
[]s
Vilc
O que o algoritmo da mochila ajuda é justamente se o operador inspeciona a fila e estima como ficarão os carros mesmo antes de embarcá-los!!!
Ou seja quais comprimentos w1, w2, w3, w4, ... serão distribuídos para maximizar W1 e W2???
[]s
Vilc
Não é verdade. Acho que faz diferença saber o comprimento de todos os carros ou só o comprimento do próximo.
Você tem razão: eu formulei mal o enunciado.
O operador sabe os comprimentos de todos os carros da fila.
Mais um detalhe: todos os comprimentos -- balsa e carros -- são inteiros.
O operador sabe os comprimentos de todos os carros da fila.
Mais um detalhe: todos os comprimentos -- balsa e carros -- são inteiros.
Algumas duvidas
Supondo:
Comprimento da balsa: b
Comprimento dos carros: c_1, c_2, ... , c_n
Seria valido o seguinte?
- Se c_1 > b, entao nehum carro pode ser colocado na balsa. Mais geral: se c_i > b com 1 <= i <= n, entao os carros i, i+1, ..., n nao podem ser colocados na balsa. (Temos que respeitar a fila).
- c_1 + c_2 + ... + c_m <= 2b com 1 <= m <= n, entao podem ser colocados no maximo m carros, se e so se c_1 + c_2 + ... + c_m + c_{m+1} > 2b. (c_{n+1} = infinito).
- o algoritmo que resolve este problema seria uma variacao do SUMA-DE-SUBCONJ.
Supondo:
Comprimento da balsa: b
Comprimento dos carros: c_1, c_2, ... , c_n
Seria valido o seguinte?
- Se c_1 > b, entao nehum carro pode ser colocado na balsa. Mais geral: se c_i > b com 1 <= i <= n, entao os carros i, i+1, ..., n nao podem ser colocados na balsa. (Temos que respeitar a fila).
- c_1 + c_2 + ... + c_m <= 2b com 1 <= m <= n, entao podem ser colocados no maximo m carros, se e so se c_1 + c_2 + ... + c_m + c_{m+1} > 2b. (c_{n+1} = infinito).
- o algoritmo que resolve este problema seria uma variacao do SUMA-DE-SUBCONJ.
Tudo isso é verdade, mas não é relevante para a solução do problema.
Prof. Paulo,
para resolver o problema tentei seguir o mesmo caminha do mochila booleana, encontrando a subestrutura ótima, fazendo a um algoritmo recursivo que resolve o problema e depois transformar para um algoritmo iterativo utilizando uma tabela.
Só que no caso da balsa, a tabela deve ser tridimensional, pois temos o tamanho de estibordo e de bombordo da balsa (diferente da mochila que só tem o tamanho dela).
É por ai, ou existe uma forma mais eficiente de resolver?
Obrigado!
Olá a todos!
Outro dúvida sobre o enunciado do problema. Pelo que entendi, devemos respeitar a fila de carros, mas o que fazer no caso do próximo carro da fila não caber em nenhuma pista e algum carro atrás dele na fila couber?
Consideramos que nenhum carro entra mais, ou podemos deixar os que cabem pular a fila?
Abraços!
Pelo que eu entendi da explicação do problema dada em aula, neste caso, nenhum carro entra mais. A fila deve ser sempre respeitada e, portanto, não podemos permitir que carros "pulem" a fila.
Exatamente. A fila deve ser respeitada.