Сумма монетами Опции

[Maski]

Даны натуральные числа m1, m2 .. mi (m1=1, mi<m(i+1) n=10) и натуральное число S. Рассматривая mi как достоинства монет и считая, что монет каждого достоинства имеется в неограниченном количестве, определить, каким минимальным числом этих монет можно получить сумму S.

Помогите, кто знает plzzz. Я написал жадный алгоритм, но он не всегда работает. Подскажите, пожалуйста, как нужно пересортировывать элементы для общего решения или предложите чего-нибудь лучше. Очень необходимо

[Алена]

Незначительная переделка вот этой программы даст то, что тебе нужно:
разложение числа

Кстати, пример, когда Greedy работает неправильно, не приведешь?

[Michael_Rybak]

Эта задача решается методом динамического программирования. Вот, почитай, разберись и переделай.

2 Алена

Есть монеты 1, 5 и 11 копеек. Надо представить число 15.

Сообщение отредактировано: Michael_Rybak - 9.12.2006 17:21

[Алена]

Пример по ссылке, которую я привела, в этом случае отрабатывает нормально - три монеты по 5 копеек...

Сообщение отредактировано: Алена - 9.12.2006 17:24

[Michael_Rybak]

Ты спросила не контрпример к той программе, а контрпример к жадному алгоритму.


А пример по ссылке работает полным перебором. Запусти для n=100, diapazon = {1..100}

[Алена]

Mr/ Michael_Rybak, и что? Где-то были указаны ограничения по быстродействию и/или количеству используемой памяти? Тогда покажите, ГДЕ? Я, например, этого не видела... Факт остается фактом, пример-то работает...

[Michael_Rybak]

Тогда покажите, ГДЕ?

Нигде не были. Но полиномиальное решение всегда лучше, чем перебор, согласись.

Факт остается фактом, пример-то работает...

Какой пример? Алена, решение volvo - не жадное, потому и работает на примере с суммой 15. ОП сказал, что жадное не работает, ты спросила, в каком случае, я привел пример.

[Maski]

uses crt;
const mn=5;
var a,b:array[1..mn]of integer;
i:integer;
flag:integer;
procedure calc(summ:integer);
var i,j,kol:integer;
begin
if flag=0 then
if summ=0 then begin
if flag=0 then begin
kol:=0;
flag:=-1;
writeln('Result:');
for i:=1 to 5 do begin
kol:=kol+b[i];
writeln(a[i],' - ',b[i]);
end;
write('VSEGO: ',kol);
end;
end else begin
for i:=mn downto 1 do begin
if summ-a[i]>=0 then begin
b[i]:=b[i]+1;
calc(summ-a[i]);
b[i]:=b[i]-1;
end;
end;
end;
end;
begin
clrscr;
for i:=1 to mn do read(a[i]);
for i:=1 to mn do b[i]:=0;
read(i);
flag:=0;
calc(i);
readkey;
end.

Написана такая программа, но , например для варианта 1 3 5 7 10 и 14 она работает неправильно, никак не могу разобраться почему. Подскажите кто-нибудь, что нужно поправить, чтобы смотрелись все варианты точно.