Рекурсия. Задача про монеты

[k1r1ch]

Ох... Я себя таким тупым чувствую, но вот очередная задача на рекурсию и снова ноль мыслей Сделал заготовку (см. ниже), по задумке Money и есть рекурсивная процедура, но вот что в ней прописывать ваще не знаю...
Вот текст задачи (если что):
|У покупателя есть n монет достоинством H(1),..., H(n). У продавца есть m монет достоинством B(1),...,B(l). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).|

program Recur;
uses Crt;
type
  TMoney = record
    Cost: integer;
    Count: integer;
  end;
var
  Sell, Buy: array [1..10] of TMoney;
  Price, i: integer;

procedure SetStartMoney;
begin
  Sell[1].Cost := 2;
  Sell[1].Count := 3;
  Sell[2].Cost := 5;
  Sell[2].Count := 4;
  Buy[1].Cost := 1;
  Buy[1].Count := 1;
  Buy[2].Cost := 3;
  Buy[2].Count := 5;
end;

procedure Money();
begin
  
end;

begin
  ClrScr;
  SetStartMoney;
  Write('Введите стоимость товара: ');
  Readln(Price);
  Money;
  repeat until keypressed;
end.

Наведите на верные мысли (и объясните, как они к вам приходят )

[ОДИНОЧЕСТВО В СЕТИ]

про монеты

[LeBron]

Да уж. Опять напишу "человеческое" (без рекурсии) решение. Задача известная, есть и на многих онлайн-АСМ-системах, и на Алголисте. Фактически можно свести к тому, что у продавца есть монеты свои и покупателя и ему необходимо с них собрать сумму, равную общей сумме минус цена вещи. Есть 2 основных способа решения. Если большие ограничения на количество монет и маленькие - на их номинал, - тогда динамикой. Если маленькие на количество и большие на номинал - тогда нерекурсивным перебором. Сейчас распишу оба способа.

[LeBron]

О, на динамическое решение уже и ссылку бросили. Тогда распишу перебор. Генерим 2ичное число из числа нолей, равного числу монет. Далее на каждом шагу будем увеличивать на 1 это число, пока не дойдем до (2^n)-1. Увеличив, составляем сумму следующим образом - если бит, соответствующий выбраной монете, равен 1, то включаем ее в сумму, иначе - нет. Если сумма равна искомой - есть ответ.
Для увеличения производительности лучше пересчитывать сумму во время самого увеличения числа на 1.

[k1r1ch]

Погодите! Динамическое программирование - это не рекурсия?! Блин, а там у темы название динамическое программирование, я думал это одно и то же! Больше не буду пытаться рекурсией сделать)

[LeBron]

Можете рекурсией, можете не рекурсией, как Вам удобно. Но если нету даже примерного представления об алгоритме решения, то рекурсия Вам не поможет.