Fórum geral de discussão

Esta foi a minha resposta:

"Você identificou uma questão crucial, mas escolheu uma solução (backtracking) que não é a melhor. Aqui é importante distinguir entre o caso geral do problema do troco e o caso particular que aparece no EP1.

No caso geral do problema do troco, nem a quantidade de tipos de moedas nem o valor de cada moeda são conhecidos de antemão. O programa deveria ler esses dados. Ele seria, portanto, suficientemente genérico para lidar com qualquer sistema monetário. Nessa formulação geral, o problema do troco é computacionalmente difícil. (De fato, é possível provar que esse problema é NP-difícil.) Note que uma solução para o problema do troco é um algoritmo com duas propriedades: (1) sempre que for houver troco, o algoritmo deve encontrá-lo, e (2) o troco encontrado deve usar o menor número possível de moedas. A técnica de "backtracking", aplicada ao problema geral do troco, produz uma solução parcial, que tem a propriedade (1) mas não a propriedade (2). Existe outra técnica, chamada "programação dinâmica", que produz uma solução com as duas propriedades.

No caso específico do EP1, entretanto, não é necessário usar nada disso! Como os valores das moedas são conhecidos de antemão (e são valores "razoáveis", no sentido de que eles têm só dois probleminhas), é possível explorar o conhecimento desses valores para criar um algoritmo simples que tem as propriedades (1) e (2). Esse algoritmo pode ser obtido modificando-se a solução "gulosa" (a que escolhe sempre a moeda de maior valor) de modo a contornar os tais dois probleminhas. E quais são os probleminhas? Bom, o que atrapalha a solução "gulosa" é a existência de algum par de cédulas ou moedas tais que nenhuma delas é múltipla da outra. Ou seja, os dois probleminhas são os pares (25, 10) e (500, 200). Note que o primeiro desses pares está na raiz do beco sem saída descrito em sua mensagem."

entao o que faremos afinal??? nao que eu esteja sem paciencia, mas eh que quando a gente resolve um problema surge outro, ta certo que nao conhecemos todas as ferramentas e etc...pelo menos eu... mas tipo temos alem do de 30 centavos e seis reais, mais tres problemas do de 105 centavos, 205 centavos e 55 centavos, que foram postados anteriormente...

esses "becos" serao testados? pq eu posso fazer dos dois primeiros e acaberem testando os outros...pq mesmo que tirem ponto pq nao fiz da do de 105 centavos 205 e 55 sempre vai ter algum gênio(...=)...) que vai descobrir outro problema, nao?? e o que garante que esse outro problema nao sera utilizado no teste dos programas????ate segunda alguem vai inventar outro aí alguns ...eu pelo menos.... vao ficar na duvida "sera que vao testar isso de verdade??"

pq nao adianta resolvermos um, dois, cinco...nao sei quem vai corrigir...mas a pergunta é para essa pessoa "quais 'problemas' voce vai testar???se alguem postar outro hj(sabado) ou domingo você vai testar este problema tb??? pq se for eu soh vou terminar mesmo segunda feira...."

esse post nao eh para ser levado no tom da ignorancia ou da impaciencia e nem da "to com preguica de fazer" mas eh que nao quero perder ponto a toa...

sem mais...=)...