1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Raciocínio para um problema de programação

Discussão em 'Programação' iniciada por PGDF, 5 de Junho de 2012. (Respostas: 10; Visualizações: 910)

  1. PGDF

    PGDF Power Member

    Boa tarde pessoal,
    Tenho um novo problema a minha frente (que bom :P), mas quanto mais olho não sei por onde pegar, não sei onde pegar mas não é em termos de programação, mas sim como fazer o meu programa processar de modo a não perder muita memoria ou a ficar segundos e segundos ate chegar ao resultado.
    Questão: como fazer para que o programa demore menos tempo possível sem perder a performance ???

    TAREFA:

    A sua tarefa é escrever um programa para calcular o preço do passe, dado o valor que administração pretende, o número máximo de notas que a máquina aceita, o conjunto dos valores que podem ser pagos com moedas e o valor nominal de cada uma das notas que a máquina aceita. O preço deve ser o menor valor maior ou igual ao preço pretendido pela administração que pode ser formado usando notas e moedas: o número de notas deve ser menor ou igual ao máximo que a máquina aceita; os valores que podem ser pagos em moedas correspondem às quantias que podem ser formadas com entre 0 e quatro moedas inclusive, e, ao contrário do problema anterior, já estão pré-calculados.

    RESTRIÇÕES:

    O número máximo de valores que podem ser introduzidos só com moedas não é especificado. O número máximo de tipos de notas que a máquina aceita também não.
    Note bem: o número de valores que podem ser introduzidos só com moedas pode ser zero (o que representaria uma situação em que a máquina não aceita moedas) e analogamente para o número de notas. No entanto, em nenhum teste esses dois números serão zero simultaneamente.
    Em todos os casos de teste o problema tem solução: isto é, existe sempre um valor maior ou igual ao preço pretendido pela administração que pode ser pago de acordo com as regras (moedas mais notas em número inferior ao igual ao máximo permitido).

    INPUT:


    A primeira linha do ficheiro de input contém um número inteiro representando o preço pretendido pela administração, em cêntimos; a segunda linha contém um número inteiro representando o número máximo de notas que a máquina aceita numa operação; seguem-se um conjunto de linhas, em número indeterminado, contendo cada uma delas um número inteiro representando um valor que pode ser pago só com moedas, expresso em cêntimos. Esse conjunto de linhas está ordenado por ordem crescente, sem repetições e termina quando surge uma linha contendo o separador -1; a seguir ao separador, seguem-se um segundo grupo de linhas, cada uma com um número, representado o valor nominal em cêntimos de cada uma das notas que a máquina aceita, por ordem crescente sem repetições.

    OUTPUT:


    O seu programa escreverá uma única linha contendo o preço para o passe, calculado de acordo com as regras apresentadas

    Exemplo 1

    Input
    550
    1
    20
    40
    60
    -1
    500

    Output

    560

    Explicação:A administração pretende que o preço do passe seja €5.50. A máquina só aceita uma nota, que pode ser de cinco euros ou de dez euros. Os valores que podem ser pagos com moedas são 20 cêntimos, 40 cêntimos ou 60 cêntimos. Logo, o valor do passe dever ser €5.60


    Exemplo 2
    Input
    5130
    3
    5
    10
    15
    20
    25
    30
    35
    40
    -1
    100
    500
    1000
    2000
    5000

    Output
    5130
    Explicação: Neste caso, o preço pretendido, 5130, pode ser aceite: moedas no valor de 30 (que é uma das quantias listadas como sendo possíveis de formar só com moedas), uma nota de 100 e uma de 5000.

    Exemplo 3
    Input
    5130
    3
    5
    10
    15
    20
    25
    30
    35
    40
    -1
    500
    1000
    2000
    5000

    Output
    5500
    Explicação:O preço pretendido é 5130. O menor valor maior ou igual a esse que se consegue é 5500, usando uma nota de 500 e uma de 5000. Neste caso, não se usam moedas.

    Exemplo 4
    Input
    305
    5
    2
    4
    6
    8
    -1
    17
    88
    Output
    306
    Explicação: 306 = 88*3 + 17*2 + 8.


    ATENÇÃO: os valores das moedas não são as moedas que existem, mas sim o conjunto dos valores que se podem fazer:
    Neste caso:
    Input
    305
    5
    2
    4
    6
    8
    -1
    17
    88

    com as moedas podemos fazer 2 centimos OU 4 centimos OU 6 centimos OU 8 centimos. NAO SE PODE juntar o 8 com o 2 e fazer 10 centimos.

    Cumps
    PGDF
     
    Última edição: 5 de Junho de 2012
  2. Flinger

    Flinger Power Member

    Faz 2 listas, uma com as notas possíveis, outra com os valores possíveis de moedas.

    Depois tentas as combinações de notas que te deixam o mais perto possível do Valor sem o ultrapassar, da maior para a mais pequena.
    A seguir testas os vários valores de moedas (ordem crescente) até encontrares aquele que ultrapasse o valor pretendido.
    Se nenhum valor o ultrapassar, voltas a testar notas. Se estiveres no número limite de notas, retiras a última que usaste.
    Vais adicionando da mais pequena para a maior até o valor total ultrapassar o pretendido.
     
  3. PGDF

    PGDF Power Member

    Obrigado pela sugestão, mas esse caso já me passou pela cabeça e não dá, imagina que o valor pretendido pela empresa é de 512.
    e tens as moedas:
    20, etc...
    e tens as notas:
    495
    500
    etc...

    como disseste uso a nota de 500 pois está mais perto do valor 512 + os 20c em moedas o preço mínimo final era de 520, mas está enrado. Se usar a nota de 495 e em moedas os 20c fico com o preço minimo de 515, sempre está mais perto do 512

    espero ter sido claro
     
  4. Flinger

    Flinger Power Member

    Se de facto tens essas restrições todas, então dificilmente vais poder usar outra solução que não passe pela brute force.

    Se poderes implementar a solução usando qualquer linguagem de programação aconselho-te usar prolog. Caso tenha de ser numa linguagem mais comum, tens de implementar uma solução que ao calcular um calor, a tente calcular outra, pegando numa nota de valor mais pequeno. Claro que esta solução se vai complicar à medida que aumentar o número de notas possíveis de usar, bem como estes valores.

    Estava a puxar pela cabeça para usar grafos, mas não vejo forma de montar um com utilidade prática.
     
  5. PGDF

    PGDF Power Member

    Só posso mesmo fazer isto em C.
    se não me lembrar de mais método nenhum, tenho criar uma lista ordenada com todos os valores possíveis que as notas possam tomar e o comprimento dessa lista ira depender do numero de notas notas existentes e também do número de notas que posso utilizar. Basta existirem a volta de 20 notas e com combinações 5 a 5 que o programa já irá demorar uns segundos a processar. O método de avaliação do programa está como tempo máximo estipulado de 1segundo, senão dá Time Limit Excedded
     
  6. Flinger

    Flinger Power Member

    Esse problema começa-me a parecer um NP.

    Como te disse, se o valor das notas for altamente variável, e podendo utilizar um número bastante grande de notas, transforma-se num problema que necessita Brute Force. Pelo menos no meu ver, pode ser que exista alguma solução que me esteja a escapar completamente.

    Dá aqui uma vista de olhos a ver se te surge alguma ideia :D
    http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante#Algoritmos_gen.C3.A9ticos
     
  7. rocksparty

    rocksparty Power Member


    Concordo com o Flinger...

    Com essa condição.. Brute force
     
  8. Flinger

    Flinger Power Member

    Acho que podes usar o algorítmo que te dei anteriormente, com algumas alterações. Depois de encontrares uma solução, continuas a procurar a próxima, ou seja, como se não tivesses a nota mais alta. Encontrando outra solução, comparas com a anterior e ficas com a melhor. Paras, quando no início de uma iteração o valor da nota * numero de notas que podes usar + o valor mais alto em moedas for menor que o valor que queres.

    Assim evitas tanto repetições (500 + 5000 e 5000 + 500), como fazer contas com notas que nunca chegam ao valor que pretendes. É um brute force com limites :D
     
  9. Não li bem o problema, mas experimenta pesquisar por Algoritmos gananciosos (greedy algorithms). Acho que para problemas de trocos é capaz de te ajudar.
     
  10. PGDF

    PGDF Power Member

    Obrigado a todos pelas sugestões e ajudas, vou pensar em todos os casos e sugestões que me deram e depois digo-vos alguma coisa
     
  11. PGDF

    PGDF Power Member

    Já consegui resolver o problema não sei se será a melhor maneira (é por isso que existe um forum para discussão). Quero opiniões.
    Imaginem as seguintes valorações de conjuntos de moedas e notas:

    Criei um array de listas, em que o índice de cada lista representa o numero de notas precisas para fazer os valores que estão contidos na mesma lista.
    Exemplo:

    Depois faço a concatenação das listas todas numa só, passo um algoritmo de ordenação e assim que encontrar o valor igual ou maior pretendido pela administração imprimo.

    Isto funciona bem, mas para números de notas máximas superiores a 40/50 já começa a demorar algum tempo

    Quero sugestões ;)
     
    Última edição: 8 de Junho de 2012

Partilhar esta Página