Жадный алгоритм. Задача о размене денег.

[Multiman]

Доброго времени суток всем! нужно написать программу на Delphi(других не знаем) которая бы разменивала некоторую сумму денег наименьшим числом купюр. Для реализации должен быть применен жадный алгоритм.

Например. имеются купюры номиналами:1руб 5руб 10 руб 50 руб 100 руб 500 руб 1000 руб 5000 руб. нужно разменять сумму например 5190руб. Программа должна выдать:сумму 5190 можно разменять 5000+100+50+10+10+10+10(ну я так себе это представляю)

В программировании я только на самом начале , поэтому даже не знаю как подступиться. Объясните пожалуйста как вообще можно это сделать. Если не сложно накидайте программу или жадный алгоритм напишите а то курсовую уже скоро сдавать)))

Заранее всем благодарен!

[Serge_Bliznykov]

у меня всегда были проблемы с динамическим программированием. НО. Т.к. число купюр каждого достоинства у Вас не ограничего, то задача решается элементарно!
помещаем все купюры в массив по уменьшению их стоимости.
Пусть надо получить число X

i (начальное значение, какие купюры брать) := 1 (т.е. сначала берём купюры самого большого достоинства)
цикл, пока X больше нуля:
   число купюр Ni их определяем как
       Ni := X div Величина_Купюры;
   выводим количество купюр Ni (с указанием достоинства)
   X := X - Величина_Купюры * Ni;
   i := i + 1;
   if i>РазмераМассиваСДостоинстомКупюр тогда begin
      Сообщение: Ошибка! Сумма не может быть получена,
            исходя из данного набора достоинств купюр!
       выход!
   end
конец цикла.
всё.

[Multiman]

ничего не понял) можно все прямо с объявления массива и переменных и вывод результата?( чисто код) да и зачем эта строчка:

if i>РазмераМассиваСДостоинстомКупюр тогда begin
Сообщение: Ошибка! Сумма не может быть получена,
исходя из данного набора достоинств купюр!
выход!
end

прога всегда должна разменивать т.к. сумма всегда будет целым числом

[Serge_Bliznykov]

прога всегда должна разменивать т.к. сумма всегда будет целым числом

При данном наборе купюр - да, такого никогда не может быть.
А вот если выкинуть из набора, например, 1 рублёвые купюры, и всё. То, что сумма целое число - может и не помочь!
Ладно. не хотите делать проверку - не делайте.

Проще код кинуть, чем разжёвывать. я и так, словами алгоритм описывал раза в три дольше, чем написал бы код. Не хотите разбираться и писать код самостоятельно - не надо. Вот решение:

const
  Kupiury : array[1..8] of integer =
    (5000, 1000, 500, 100, 50, 10, 5, 1);
var
  X : integer;
  i, Ni : integer;
  s : string;
begin
  X := StrToInt(Edit1.Text);
  s := '';

  i := 1;
  while X>0 do begin
    Ni := X div Kupiury[i];
    if Ni>0 then
      s := s + ' '+IntToStr(Ni)+'*'+
                   IntToStr(Kupiury[i])+' ';
    X := X - Ni * Kupiury[i];
    i := i + 1;
 end;
 Edit2.Text := s;
end;

[Multiman]

Спасибо вам огромное!
Когда написали код, то сразу же все стало ясно=) А то я маленько запутался в вашем алгоритме. Я просто еще не умею программировать и в алгоритмах плохо разбираюсь, а в техникуме особо не напрягаются нас учить и что-то объяснять... Вот и приходиться самим во всем разбираться. А вы уже профессионал и для вас это разминка)
Еще раз большое спасибо за то что не проигнорировали и помогли.