Жадный алгоритм и перебор

[mailjaffka]

Помогите реализовать жадный алгоритм и простой перебор (либо рекурсия) для задачи:
"Есть по 2 монеты достоинств а1,а2 ... аn. Можно ли этими монетами оплатить сумму S?"
Количество номиналов, сами номиналы и сумму вводим с клавиатуры

[sabbathist]

Вообще, тут жадный алгоритм не подходит. Это классическая задача на "рюкзак".

[mailjaffka]

нужно реализовать 3 алгоритма для этой задачи

[LeBron]

Могу скинуть сорс для Монетки - 2 из АСМП, оптимальное алгоритмически (хотя и не самая быстрая реализация) решение для тех ограничений - полный перебор.

Жадный можно использовать только как евристику при больших ограничениях, но очень маленький шанс, что он найдет правильное решение при его наличии.

Третий алгоритм - динамика, наверно. При маленьких номиналах и большом количестве монет лучше перебора.

[Serge_Bliznykov]

Жадный можно использовать только как евристику

евристика - это то, что используют умные евреи?..

извините, не удержался...

[LeBron]

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

евристика - это то, что используют умные евреи?..

извините, не удержался...

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

На тему жадника - подумал, еще вроде учат писать "заполнение с откатом", тоесть попробовали набрать нужную сумму, если перебор - заменяем одну из монет на более мелкую, и снова пробуем...В общем, шанс срабатывания как бы больше, но и время работы тоже больше. Такой же бред, так лобовой жадник.

[mailjaffka]

была бы очень признательна

[mailjaffka]

на самом деле мне просто тремя способами нужно реализовать задачу

[mailjaffka]

на самом деле мне просто тремя способами нужно реализовать задачу

[LeBron]

var input,output:text; n,i,j,g,nm,ans,t:integer;ara:array[0..1000] of integer;ar,arq:array[0..1000] of integer; ts,sum,a:integer;
begin
assign(input,'input.txt');reset(input);assign(output,'output.txt');rewrite(output);
readln(input,a,n);                                    ans:=10000;
for i:=1 to n do begin read(input,ar[i]);ts:=ts+2*ar[i];end;if ts<a then writeln(output,'-1') else begin
ara[1]:=3;for i:=2 to 15 do begin ara[i]:=3*ara[i-1];end;
for i:=1 to ara[n] do begin{ for t:=1 to n do write(arq[t]);writeln('   ',sum,' ',nm);}{sum:=0;nm:=0; }
if arq[n]<2 then begin inc(arq[n]);sum:=sum+ar[n];inc(nm);end else begin g:=n;while arq[g]>1 do begin sum:=sum-ar[g]*arq[g];dec(nm,arq[g]);
arq[g]:=0;dec(g);end;
inc(arq[g]);sum:=sum+ar[g];inc(nm);end;{for j:=1 to n do begin sum:=sum+ar[j]*arq[j];nm:=nm+arq[j];end;}if sum=a then begin
if nm<ans then ans:=nm;end;end; if ans>1000 then writeln(output,'0') else writeln(output,ans);   end;
close(output);close(input);
end.

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