Сумма монетами |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Сумма монетами |
Maski |
Сообщение
#1
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Репутация: 0 |
Даны натуральные числа m1, m2 .. mi (m1=1, mi<m(i+1) n=10) и натуральное число S. Рассматривая mi как достоинства монет и считая, что монет каждого достоинства имеется в неограниченном количестве, определить, каким минимальным числом этих монет можно получить сумму S.
Помогите, кто знает plzzz. Я написал жадный алгоритм, но он не всегда работает. Подскажите, пожалуйста, как нужно пересортировывать элементы для общего решения или предложите чего-нибудь лучше. Очень необходимо |
Алена |
Сообщение
#2
|
Гость |
Незначительная переделка вот этой программы даст то, что тебе нужно:
разложение числа Кстати, пример, когда Greedy работает неправильно, не приведешь? |
Michael_Rybak |
Сообщение
#3
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Эта задача решается методом динамического программирования. Вот, почитай, разберись и переделай.
2 Алена Есть монеты 1, 5 и 11 копеек. Надо представить число 15. Сообщение отредактировано: Michael_Rybak - |
Алена |
Сообщение
#4
|
Гость |
Пример по ссылке, которую я привела, в этом случае отрабатывает нормально - три монеты по 5 копеек...
Сообщение отредактировано: Алена - |
Michael_Rybak |
Сообщение
#5
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Ты спросила не контрпример к той программе, а контрпример к жадному алгоритму.
А пример по ссылке работает полным перебором. Запусти для n=100, diapazon = {1..100} |
Алена |
Сообщение
#6
|
Гость |
Mr/ Michael_Rybak, и что? Где-то были указаны ограничения по быстродействию и/или количеству используемой памяти? Тогда покажите, ГДЕ? Я, например, этого не видела... Факт остается фактом, пример-то работает...
|
Michael_Rybak |
Сообщение
#7
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Тогда покажите, ГДЕ? Нигде не были. Но полиномиальное решение всегда лучше, чем перебор, согласись. Цитата Факт остается фактом, пример-то работает... Какой пример? Алена, решение volvo - не жадное, потому и работает на примере с суммой 15. ОП сказал, что жадное не работает, ты спросила, в каком случае, я привел пример. |
Maski |
Сообщение
#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 она работает неправильно, никак не могу разобраться почему. Подскажите кто-нибудь, что нужно поправить, чтобы смотрелись все варианты точно. |
Текстовая версия | 5.10.2024 9:59 |