IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Сумма монетами
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 3
Пол: Мужской

Репутация: -  0  +


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

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


Гость






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

Кстати, пример, когда Greedy работает неправильно, не приведешь?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

2 Алена

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

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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

Сообщение отредактировано: Алена -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


А пример по ссылке работает полным перебором. Запусти для n=100, diapazon = {1..100}
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


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

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


Какой пример? Алена, решение volvo - не жадное, потому и работает на примере с суммой 15. ОП сказал, что жадное не работает, ты спросила, в каком случае, я привел пример.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8





Группа: Пользователи
Сообщений: 3
Пол: Мужской

Репутация: -  0  +


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 она работает неправильно, никак не могу разобраться почему. Подскажите кто-нибудь, что нужно поправить, чтобы смотрелись все варианты точно.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 5.10.2024 9:59
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name