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

cyberops

[algoritmo] menor troco

12 mensagens neste tópico

Boas,

estou aqui com um problema para achar um algoritmo para achar o menor troco.

ja fiz o codigo para determinar se o troco realmente existe mas caso ele n existe tenho q determinar um possivel troco com o menor numero de moedas. por exemplo

exemplo sem troco possivel:

troco = 11 %% com moedas dos tipos 10 e 5

1 10

1 5

int [] moedas = new int[]{25, 20, 13, 7, 5, 3}; /*tem que estar ordenado decrescentemente*/
int [] nmoedas = new int[moedas.lenght]
while(soma!=troco && i<moedas.length){				

if(troco>=moedas[i]){
	j=i;
	while(j<moedas.length){
		System.out.println("adicionou: "+moedas[j]);
		soma+=moedas[j];
		nmoedas[j]+=1;

		if(soma>troco){
			System.out.println("retirou: "+moedas[j]);							
			soma-=moedas[j];
			System.out.println("soma: "+soma);
			nmoedas[j]-=1;
			j++;
		}else if(soma==troco){
			System.out.println("certo");
			return nmoedas;
		}						
	}
	soma-=moedas[i];
	nmoedas[i]-=1;
	i++;
}else
	i++;

se calhar tenho q arranjar outro forma de determinar o menor troco para ter sempre uma referencia para o melhor troco até ao final, nao?

e se calhar tenho q fazer todas as combinaçoes possiveis, claro q retirando sempre as somas que excedem o troco

cumps

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso é uma variação do algoritmo "Knapsack problem"

http://en.wikipedia.org/wiki/Knapsack_problem

Eu começava por preencher o troco com as moedas maiores disponiveis. Sempre que ultrapassar o troco mudas para uma moeda menor. Isto até bater no troco certo.

exacto. é o q faço no codigo acima, mas caso n haja troco certo para dar é preciso dar troco, recorrendo ao menor numero de moedas tem que ser por excesso, como tenho no exemplo acima:

a maq tem q dar troco de 11 e so tem moedas de 10 e 5. Ou seja, a maquina vai dar uma de 10 e outra de 5.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Uma versão muito rudimentar em Python,

moedas = {200: "2 euros", 100: "1 euro", 50: "50 cêntimos", 20: "20 cêntimos", 10: "10 cêntimos", 5: "5 cêntimos", 2: "2 cêntimos", 1: "1 cêntimo"]
valor = int(raw_input("Insira o valor a devolver ao cliente em cêntimos: "))

troco = {}
for moeda in moedas:
    if valor == 0: break
    while valor >= moeda:
        try: troco[moeda] += 1
        except KeyError: troco[moeda] = 1

if troco == {}:
    if valor != 0: print "Não temos moedas para fazer o troco."
    else: print "Não é suposto dar troco..."
else:
    if valor != 0: print "Não temos moedas para fazer o troco certo, estamos a dever %i cêntimos." % valor
    print "Troco:"
    for moeda in troco:
        print "%i moeda(s) de %s" % (troco[moeda], moedas[moeda])

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Uma versão muito rudimentar em Python,

moedas = {200: "2 euros", 100: "1 euro", 50: "50 cêntimos", 20: "20 cêntimos", 10: "10 cêntimos", 5: "5 cêntimos", 2: "2 cêntimos", 1: "1 cêntimo"]
valor = int(raw_input("Insira o valor a devolver ao cliente em cêntimos: "))

troco = {}
for moeda in moedas:
    if valor == 0: break
    while valor >= moeda:
        try: troco[moeda] += 1
        except KeyError: troco[moeda] = 1

if troco == {}:
    if valor != 0: print "Não temos moedas para fazer o troco."
    else: print "Não é suposto dar troco..."
else:
    if valor != 0: print "Não temos moedas para fazer o troco certo, estamos a dever %i cêntimos." % valor
    print "Troco:"
    for moeda in troco:
        print "%i moeda(s) de %s" % (troco[moeda], moedas[moeda])

n vejo mto de pyton, mas acho q o q fazes ai ja eu tenho feito em java. so que tu estas a considerar q se n houver moedas q satisfaçam o troco, a maquina n da troco, enquanto q no meu caso tenho q dar ;)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso não funciona.

Imaginem o seguinte exemplo:

Moedas de 1 5 8 e 10. Pretendemos obter o valor 13.

Seguindo o vosso método, 10+1+1+1=13, logo 4 moedas.

Mas 5+8 = 13 usando somente duas moedas.

Para resolver o problema tens que pensar na seguinte recursividade:

min(13) = 1 + minimo(min(13-10),min(13-8),min(13-5),min(13-1)).

Sendo min(0) = 0, obviamente.

O número mínimo de moedas para formar o valor 13 pode ser o número mínimo de moedas para formar 3+a moeda 10, ou o número mínimo de moedas para formar 5 + a moeda 8 etc..

Podes resolver isto recursivamente implementa simplesmente a função que disse em cima (memoization, ou tabulação em português, pode servir para acelerar o resultado) ou usar programação dinâmica para construires um vector v[valor que pretendemos] com 2 ciclos for.

Não sei porquê acho que já expliquei a solução deste problema anteriormente aqui no forum..

Já agora uma informação extra para o shumy: knapsack permite-te saber se consegues formar o troco com as moedas que tens disponíveis, mas não te diz que moedas dar se pretendes entregar o menor número possível.

Existindo esta solução de programação dinâmica, obtemos esta solução mais eficiente do que knapsack, mas de facto muitos problemas semelhantes a este teriam que ser resolvidos com knapsack. (inteiro neste caso, pois existem vários tipos).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isso não funciona.

Imaginem o seguinte exemplo:

Moedas de 1 5 8 e 10. Pretendemos obter o valor 13.

Seguindo o vosso método, 10+1+1+1=13, logo 4 moedas.

Mas 5+8 = 13 usando somente duas moedas.

Para resolver o problema tens que pensar na seguinte recursividade:

min(13) = 1 + minimo(min(13-10),min(13-8),min(13-5),min(13-1)).

Sendo min(0) = 0, obviamente.

O número mínimo de moedas para formar o valor 13 pode ser o número mínimo de moedas para formar 3+a moeda 10, ou o número mínimo de moedas para formar 5 + a moeda 8 etc..

Podes resolver isto recursivamente implementa simplesmente a função que disse em cima (memoization, ou tabulação em português, pode servir para acelerar o resultado) ou usar programação dinâmica para construires um vector v[valor que pretendemos] com 2 ciclos for.

n percebi muito bem isto: min(13) = 1 + minimo(min(13-10),min(13-8),min(13-5),min(13-1)).

tens duas funcoes min e minimo, mas q parametros tenho q passar? o troco a subtrair com as moedas existentes?

ja agora posso usar programacao dinamica para guardar calculos ja efectuados para evitar chamar desnecessariamente outra vez a funcao, nao?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

min(13)  é o número minimo de moedas para destrocar 13

minimo(...)  é o calculo do menor valor entre os argumentos.

Se usares uma função recursiva, pesquisas a tabela de programação dinamica para ver se o valor foi calculado, se sim retornas logo o valor, senão calculas e guardas na tabela.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

min(13)  é o número minimo de moedas para destrocar 13

minimo(...)  é o calculo do menor valor entre os argumentos.

Se usares uma função recursiva, pesquisas a tabela de programação dinamica para ver se o valor foi calculado, se sim retornas logo o valor, senão calculas e guardas na tabela.

tipo isto:

int [] moedas = new int[]{10, 8, 5, 1};
int [] nMinimoMoedas = new int[moeda.lenght];
int troco = 13;
int i=0;

public void minimo(int i){
   if(i=0) return; //caso base
   else{
      nMinimoMoedas[i]=troco-moedas[i];
      minimo(i++);
   }
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não!

Deves inicializar o array nMinimoMoedas com um valor que indique que ainda não calculaste o número de moedas.

A função devia retornar um int.

Depois do caso base, deves ver se o troco de i já foi calculado. Se sim retornas esse valor senão procedes ao calculo do minimo. 

O minimo é calculado como o Warrior referiu. Tens de calcular o minimo de moedas necessario para destrocar i-moedas[j] , sendo moedas[j] cada uma das moedas do array de moedas que tens.

PS: usa a tag

 para postar código
0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

ja fiz a recursiva :cheesygrin:. agora como faço isto recorrendo a programaçao dinamica?

public void comparaArraysE(int [] numMoedas){
	existeSolucao=true;
	if(numMoedasFinal[indexNumMoedasTotal]==0){
		numMoedasFinal=numMoedas.clone();
	}else{

		if(numMoedasFinal[indexValorTotal]==0 && numMoedas[indexNumMoedasTotal]<numMoedasFinal[indexNumMoedasTotal])
			numMoedasFinal=numMoedas.clone();
		else if(numMoedasFinal[indexValorTotal]!=0)
			numMoedasFinal=numMoedas.clone();
	}
}

//metodo que vai comparar uma solucao sem troco certo, com a melhor solucao até ao momento
public void comparaArrays(int [] numMoedas){

	//primeira vez que é adicionado uma solucao ao array
	if(numMoedasFinal[indexNumMoedasTotal]==0){
		numMoedasFinal=numMoedas.clone();
	}else{
		if(numMoedas[indexValorTotal]!=0){
			if(numMoedasFinal[indexValorTotal]<numMoedas[indexValorTotal]){
				numMoedasFinal=numMoedas.clone();
			}else if(numMoedasFinal[indexValorTotal]==numMoedas[indexValorTotal]){
				if(numMoedasFinal[indexNumMoedasTotal]>numMoedas[indexNumMoedasTotal]){
					numMoedasFinal=numMoedas.clone();
				}
			}
		}
	}
}

//metodo recursivo usado para determinar
public void chamaRec(int valTrocoTMP, int [] numMoedas){
	if(valTrocoTMP==0){
		comparaArraysE(numMoedas);
	}else if(valTrocoTMP>0){

		for(int j=0; j<moedas.length; j++){
			valTrocoTMP-=moedas[j];
			numMoedas[j]+=1;
			numMoedas[indexValorTotal]= valTrocoTMP;
			numMoedas[indexNumMoedasTotal]+=1;
			chamaRec(valTrocoTMP, numMoedas);
			numMoedas [j] -=1 ;
			numMoedas[indexValorTotal]+=moedas[j];
			numMoedas[indexNumMoedasTotal] -=1;
			valTrocoTMP+=moedas[j];

		}

	}else if(valTrocoTMP<0){
		comparaArrays(numMoedas);
	}		
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ouch, essa solução está grande demais.

É possível fazer o mesmo em MUITO menos linhas de código, já usando DP.

Não vale muito a pena tentar-te explicar, tenta perceber este código em C++.

#include <iostream>
#include <string.h>

using namespace std;

int dp[1000];
int moedas[]={1,5,8,10},nmoedas=4;

int troco(int k) {
  //Se ja conhecermos o valor de troco(13) podemos devolver
  if (dp[k]>=0)
    return dp[k];
  
  //senao calculamos
  
  //colocar minsofar=2^29 (um valor grande simular "infinito")
  int minsofar=1<<29;

  //Percorremos as moedas
  for (int i=0;i<nmoedas;i++) 
    if (moedas[i]<=k) {
      //se usar essa moeda significa um numero menor de moedas ate agora encontrado, guardamos
      if (troco(k-moedas[i])+1<minsofar)
minsofar=troco(k-moedas[i])+1;
    }
    else
      break;

  //Sabemos o numero minimo de moedas para obter k, guardamos e devolvemos
  dp[k]=minsofar;
  return dp[k];
}

int main() {
  //Inicializar os elementos de dp a -1
  memset(dp,sizeof(dp),0xFF);
  
  //Fazer o valor 0 necessita de 0 moedas, é o caso baso
  dp[0]=0;
  
  //Achar troco de 13
  cout << troco(13) << endl;
  return 0;
}

Este código serve para achar o número mínimo de moedas, para conhecer ao certo as moedas é trivial acrescentar: a cada posição de DP adicionas uma moeda, a indicar que foi a que usaste. Imagina moeda[13]=5.

Sabes que para fazer o valor 13, usaste a moeda 5. De seguida, vais a moeda[13-5], ou seja, moeda[8], e vais ver que moeda usaste para fazer 8. Usaste mesmo a de 8. Como 8-8 = 0, acabaste.

Ou seja, basta adicionar um vector que te guarde uma moeda.

Se retirares os comentários o código fica minúsculo.

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