Точная сдача - алгоритм

[Dmitriy1991]

Подскажите алгоритм
У покупателя есть n монет достоинством H1, …,  Hn, а у продавца есть m монет достоинством B1, …,  Bm. Может ли покупатель приобрести вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима)?

Формат входного файла

Первая строка содержит три целых числа n, m и S, разделённых пробелом (1 ≤ n ≤ 100, 0 ≤ m ≤ 100, 1 ≤ S ≤ 2 000 000 000). Следующие две строки содержат разделённые пробелом достоинства монет покупателя и продавца соответственно (все числа натуральные, не превосходящие 100).
Формат выходного файла

Единственная строка должна содержать ответ Yes или No.
Пример

input.txt
3 3 36
12 22 23
12 21 1

output.txt
Yes

[evg_m]

два массива
1. перечень используемых монет M[1..n+m] /M[1..200]
ВСЕХ! покупателя со знаком + и продавца со знаком -.
2. индикаторы(0|1) использования данной монеты в расчете. R[1..200]

x:=0; i:=1 to n+m x:=x +M[i]*R[i]; //выплаченная сумма с учетом полученной сдачи

осталось придумать алгоритм тотального перебора ВСЕХ вариантов заполнения R (от 000...00 до 111...11 ).
P.S. где-то когда-то на этом самом форуме данная задача решалась и не один даже раз и даже я участвовал.

[Serge_Bliznykov]

Эта задача на нашем форуме - Задача про монеты

а ещё тут смотрели?


http://algolist.manual.ru/olimp/rec_prb.php#z7

Задача 7.

У покупателя есть n монет достоинством H(1),..., H(n). У продавца есть m монет достоинством B(1),...,B(l). Может ли купить покупатель вещь стоимости S так, чтобы у продавца нашлась точная сдача (если она необходима).


[Решение]

[Dmitriy1991]

Мне динамикой нужно сделать

[Serge_Bliznykov]

Сообщение от Dmitriy1991

Мне динамикой нужно сделать

так на algolist решение как раз через динамику (если я правильно понял смысл).