[algoritmo] menor troco

cyberops · February 28, 2008 at 08:05 PM

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

shumy · February 28, 2008 at 08:18 PM

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.

cyberops · February 28, 2008 at 08:56 PM

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.

djthyrax · February 28, 2008 at 09:05 PM

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

cyberops · February 28, 2008 at 10:04 PM

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 😉

Warrior · February 28, 2008 at 10:27 PM

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

cyberops · March 1, 2008 at 01:26 PM

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?

mogers · March 1, 2008 at 02:36 PM

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.

cyberops · March 1, 2008 at 03:07 PM

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

mogers · March 1, 2008 at 04:37 PM

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

cyberops · March 8, 2008 at 10:39 AM

ja fiz a recursiva 😁. 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);
	}		
}

Warrior · March 8, 2008 at 11:19 AM

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.

hudson · January 6, 2020 at 01:23 AM

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

Sign In

[algoritmo] menor troco

Recommended Posts

cyberops

shumy

cyberops

djthyrax

cyberops

Warrior

cyberops

mogers

cyberops

mogers

cyberops

Warrior

hudson

Create an account or sign in to comment

Create an account

Sign in

Home

Activity

Revista PROGRAMAR

Important Information