Даны натуральные числа m1, m2 .. mi (m1=1, mi<m(i+1) n=10) и натуральное число S. Рассматривая mi как достоинства монет и считая, что монет каждого достоинства имеется в неограниченном количестве, определить, каким минимальным числом этих монет можно получить сумму S.
Помогите, кто знает plzzz. Я написал жадный алгоритм, но он не всегда работает. Подскажите, пожалуйста, как нужно пересортировывать элементы для общего решения или предложите чего-нибудь лучше. Очень необходимо
Незначительная переделка вот этой программы даст то, что тебе нужно:
http://forum.pascal.net.ru/index.php?s=&showtopic=6327&view=findpost&p=47388
Кстати, пример, когда Greedy работает неправильно, не приведешь?
Эта задача решается методом динамического программирования. http://forum.pascal.net.ru/index.php?s=&showtopic=13631&view=findpost&p=79415, почитай, разберись и переделай.
2 Алена
Есть монеты 1, 5 и 11 копеек. Надо представить число 15.
Пример по ссылке, которую я привела, в этом случае отрабатывает нормально - три монеты по 5 копеек...
Ты спросила не контрпример к той программе, а контрпример к жадному алгоритму.
А пример по ссылке работает полным перебором. Запусти для n=100, diapazon = {1..100}
Mr/ Michael_Rybak, и что? Где-то были указаны ограничения по быстродействию и/или количеству используемой памяти? Тогда покажите, ГДЕ? Я, например, этого не видела... Факт остается фактом, пример-то работает...
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 она работает неправильно, никак не могу разобраться почему. Подскажите кто-нибудь, что нужно поправить, чтобы смотрелись все варианты точно.