Pelo o que eu entendi, o código abaixo faz a tarefa. O resultado é o seguinte (usei os dados do exemplo).
Valor: R$ 1550,00
2 PADARIA 230.0
1 MERCADO 1320.0
Valor: R$ 769,00
5 LOJA 89.0
4 ALUGUEL 450.0
2 PADARIA 230.0
Valor: R$ 800,00
Não foi encontrado nada
Eu uso recursividade no programa, isto é, uma função que chama ela mesma. Por esse motivo os itens são incluídos no vetor de trás para frente. Para quem não está acostumado, é difícil entender a primeira vista. Eu testo as combinações. Há três condições de parada:
- Eu achei uma sequência de notas cuja soma é igual ao total fornecido
- A soma da minha sequência de notas ultrapassou o total
- Verifiquei todas as combinações
As funções main e imprime é só para mostrar como a classe Pagamento funciona. Eu uso o tipo long internamente na classe Pagamento para fazer os cálculo porque a representação de ponto flutuante (número com casas decimais) pode dar problemas, principalmente em comparações, pois o computador não consegue armazenar internamente de forma exata o número 2,19, por exemplo.
Espero que ajude.
Leila
[code]import java.util.ArrayList;
public class Pagamento {
private ArrayList<Item> _meusItens = new ArrayList<Item>();
/**
* Adiciona um novo item à lista
* @param numeroControle
* @param empresa
* @param valor
*/
public void adicionaItem(int numeroControle, String empresa, float valor){
Item item = new Item(numeroControle, empresa, valor);
_meusItens.add(item);
}
/**
* Retorna o vetor com todos os itens que possuem a dada soma,
* se não haver nenhuma situação, o vetor possui tamanho 0
* @param soma a soma que precisa ser encontrada
* @return o vetor com todos os itens que possuem a dada soma
*/
public Item[] encontraItens(float total) {
long l_total = (long)(total * 100 + 0.5);
ArrayList<Item> listaItens = new ArrayList<Item>();
encontraItens (0, l_total, 0, listaItens);
listaItens.toArray(new Item[0]);
return listaItens.toArray(new Item[0]);
}
private boolean encontraItens (long soma, long total, int posicao, ArrayList<Item> itens) {
boolean encontrou = false;
for (int i=posicao; i < _meusItens.size() && !encontrou; i++) {
if (soma + _meusItens.get(i).getLValor() == total) {
itens.add(_meusItens.get(i));
encontrou = true; // encontrei a soma !!!
} else if (soma + _meusItens.get(i).getLValor() < total) {
encontrou = encontraItens (soma + _meusItens.get(i).getLValor(),
total, i+1, itens);
if (encontrou) {
//adiciona o item só se a soma for encontrada
itens.add(_meusItens.get(i));
}
}
}
return encontrou;
}
/**
* Representa um Item
*/
public class Item {
private int _numeroControle;
private String _empresa;
private long _valor;
public Item(int numeroControle, String empresa, float valor){
_numeroControle = numeroControle;
_empresa = empresa;
_valor = (long)(valor*100+0.5); //evita erros de arrendodamento
}
/**
* @return the _numeroControle
*/
public int getNumeroControle() {
return _numeroControle;
}
/**
* @return the _empresa
*/
public String getEmpresa() {
return _empresa;
}
/**
* @return the _valor
*/
public long getLValor() {
return _valor;
}
public float getValor() {
return _valor / 100.0f;
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Pagamento pag = new Pagamento();
Pagamento.Item itens[];
pag.adicionaItem (1,"MERCADO",1320);
pag.adicionaItem (2,"PADARIA",230);
pag.adicionaItem (3,"FARMACIA",315);
pag.adicionaItem (4,"ALUGUEL",450);
pag.adicionaItem (5,"LOJA", 89);
pag.adicionaItem (6,"AÇOUGUE",144);
itens = pag.encontraItens(1550);
System.out.println("Valor: R$ 1550,00 ");
imprime(itens);
itens = pag.encontraItens(769);
System.out.println("Valor: R$ 769,00 ");
imprime(itens);
itens = pag.encontraItens(800);
System.out.println("Valor: R$ 800,00 ");
imprime(itens);
}
public static void imprime(Pagamento.Item itens[]) {
if (itens.length==0) {
System.out.println("Não foi encontrado nada");
}else {
for (int i=0; i < itens.length; i++) {
System.out.println(itens[i].getNumeroControle()+" "+itens[i].getEmpresa()+" "+itens[i].getValor());
}
}
}
}
[/code]