Jump to content
cyberops

[algoritmo] menor troco

Recommended Posts

cyberops

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

Share this post


Link to post
Share on other sites
shumy

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.


Aqui há coisa de 2 anos fazia umas malhas de croché, depois fartei-me e fui para informática!

Share this post


Link to post
Share on other sites
cyberops

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.

Share this post


Link to post
Share on other sites
djthyrax

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ão peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Share this post


Link to post
Share on other sites
cyberops

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

Share this post


Link to post
Share on other sites
Warrior

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

Share this post


Link to post
Share on other sites
cyberops

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?

Share this post


Link to post
Share on other sites
mogers

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.


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
cyberops

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++);
   }
}

Share this post


Link to post
Share on other sites
mogers

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

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
cyberops

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);
	}		
}

Share this post


Link to post
Share on other sites
Warrior

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.

Share this post


Link to post
Share on other sites
hudson

https://exerciciodeprogramacao.blogspot.com/2020/01/faca-um-programa-em-c-utilizando-vetor.html

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.