Duvida com algoritimo

Delphi

10/01/2005

Olá Pessoal boa tarde,

eu preciso desenvolver um algoritimo mas estou com algumas dúvidas, deixa em explicar inicialmente o q eu quero fazer.
é um programa de cadastro de cheques, até ai sem problemas, mas apos ter os cheques cadastrados eu vou ter que exibir uma tela com todos os cheques.. no final dessa tela vai existir um campo onde o usuário informa quanto em cheque ele quer dar baixa. por exemplo.

Cliente______________Vencimento_______Valor

xxxxxxxxxxxxxxxxxxxx____01/02/2005________25.00
zzzzzzzzzzzzzzzzzzzz____05/02/2005________45.00
wwwwwwwwwwwww___06/04/2005________65.00

Caso o usuário informa-se o valo de 70 reais o sistema iria automaticamente marcar o primeiro e o terceiro (25+45) cheque pra dar baixa, caso informa-se 110 reais ele marcaria o segundo e o terceiro cheque (45+65) e assim vai...

alguem ja viu algum algoritimo que faça esse tipo de calculo, desde ja eu agradeço a todos.

[]s
Cristiano


Tineks

Tineks

Curtidas 0

Respostas

Motta

Motta

10/01/2005

Conheço isto como BRIEFCASE ALGORITHM, procure no google para mais detalhes


GOSTEI 0
Tineks

Tineks

10/01/2005

Olá Motta,

obrigado pela ajuda, estarei procurando mais informações a respeito desse algoritimo.

[]s
Cristiano


GOSTEI 0
Marcelo_mileris

Marcelo_mileris

10/01/2005

Olá, eu desenvolvi a um tempinho (Semana passada) um código para dar baixa em parcelas para um bazar. Digamos que tenha:

1ª Parcela - R$ 10,00
2ª Parcela - R$ 10,00
3ª Parcela - R$ 10,00

e o cliente vai pagar digamos que R$ 15,00 então fica assim

1ª Parcela - R$ 0,00
2ª Parcela - R$ 5,00
3ª Parcela - R$ 10,00

assim como ele pagar R$ 25,00

1ª Parcela - R$ 0,00
2ª Parcela - R$ 0,00
3ª Parcela - R$ 5,00

É isso que deseja?


GOSTEI 0
Bacalhau

Bacalhau

10/01/2005

Se bem percebi, o problema é mais ou menos este:

Dados n cheques, o cliente pretende definir o valor de um depósito no banco.

Então o programa procura se tem o cheque nesse valor e selecciona-o.

Se não tiver, procura por um par de cheques cuja combinação dê o valor

Se não tiver, repete o processo com 3 cheques (testando todas as combinaçãoes possiveis) e por aí fora.

Se conseguir o valor selecciona-os. Caso contrário informa o utilizador que não existe a combinação.

É isto?


GOSTEI 0
Beppe

Beppe

10/01/2005

Aí, resolveu seu problema? Se me mandar um cheques eu resolvo! (brincadeira)

Isto fica pra posteridade então:
const
  TCheques = 13;

var
  Cheques: array[0..TCheques - 1] of Integer = (10, 25, 45, 50, 65, 80, 90, 112, 200, 250, 320, 540, 789);
  Baixa: array[0..TCheques - 1] of Boolean;

function DarBaixa1(Valor: Integer): Boolean;
var
  Topo, Cor, Dev: Integer;
begin
  Topo := High(Cheques);
  while Topo >= 0 do
  begin
    FillChar(Baixa, SizeOf(Baixa), 0);
    Cor := Topo;
    Dev := Valor;
    while Cor >= 0 do
    begin
      if Cheques[Cor] <= Dev then
      begin
        Baixa[Cor] := True;
        Dec(Dev, Cheques[Cor]);
        if Dev = 0 then
        begin
          Result := True;
          Exit;
        end;
      end;
      Dec(Cor);
    end;
    Dec(Topo);
  end;
  Result := False;
end;

function DarBaixa2(Valor: Integer): Boolean;

  function _DarBaixa(Valor, Max: Integer): Boolean;
  var
    Topo, Cor, Dev: Integer;
  begin
    Topo := Max;
    while Topo >= 0 do
    begin
      FillChar(Baixa, Max + 1, 0);
      Cor := Topo;
      Dev := Valor;
      while Cor >= 0 do
      begin
        if Cheques[Cor] <= Dev then
        begin
          Baixa[Cor] := True;
          Dec(Dev, Cheques[Cor]);
          if (Dev = 0) or _DarBaixa(Dev, Cor - 1) then
          begin
            Result := True;
            Exit;
          end;
        end;
        Dec(Cor);
      end;
      Dec(Topo);
    end;
    FillChar(Baixa, Max + 1, 0);
    Result := False;
  end;

begin
  Result := _DarBaixa(Valor, High(Cheques));
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  Indice: Integer;
begin
  ListBox1.Clear;
  if DarBaixa2(StrToInt(Edit1.Text)) then
  begin
    for Indice := 0 to High(Cheques) do
    begin
      if Baixa[Indice] then
        ListBox1.Items.Add(IntToStr(Cheques[Indice]));
    end;
  end;
end;


Note que o array de cheques está ordenado de forma não-decrescente. Se precisar ordenar adapte a rotina QuickSort que está em Classes.pas.
O algoritmo tenta dar baixa nos cheques maiores, e se um estourar, desfaz e continua com o cheque estritamente mais baixo que ele.

Use DarBaixa2. O primeiro é greedy, e não funciona para certas combinações de cheques. É mais rápido, justamente porque não tenta todas as combinações. O segunda tenta todas as combinações válidas, descarta aquelas que não chegam a uma solução.


GOSTEI 0
POSTAR