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

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.04.2010, 21:33
Новичок

Отправить личное сообщение для Лили Посмотреть профиль Найти все сообщения от Лили
 
Регистрация: 18.04.2010
Сообщений: 4

Сдача минимальным количеством монет
Сама задача звучит так: выдать определенную сумму денег минимальным количеством монет. Т.е. у нас есть массив, в котором записано, сколько монет каждого достоинства у нас есть; есть переменная, обозначающая, какую сумму необходимо выдать.
Нужно сгенерировать всевозможные варианты (перестановок? С повторениями?) и из них выбрать минимальную.

Проблема возникает именно с тем, как сгенерировать все варианты...
  #2  
Старый 18.04.2010, 21:59
гость

 
Сообщений: n/a

Ссылку на источник задачи в студию.

Сообщение от Лили Посмотреть сообщение
Проблема возникает именно с тем, как сгенерировать все варианты...
Да понятно как - рекурсией, как же еще.

Но можно и не перебирать варианты, а решить динамическим программированием.
  #3  
Старый 18.04.2010, 22:15
Новичок

Отправить личное сообщение для Лили Посмотреть профиль Найти все сообщения от Лили
 
Регистрация: 18.04.2010
Сообщений: 4

Сообщение от гость
Ссылку на источник задачи в студию.
Источник - методичка)
Кстати на счет того, чтобы не перебирать варианты... требуют именно с перебором всех.
  #4  
Старый 18.04.2010, 23:10
гость

 
Сообщений: n/a

ну, перебирай для каждого достоинства монеты, сколько таких монет брать - от 0 до числа монет этого достоинства.
  #5  
Старый 19.04.2010, 01:37
гость

 
Сообщений: n/a

Монеты
Пасс к логину не помню, стукни в аську
374243274
  #6  
Старый 19.04.2010, 01:39
гость

 
Сообщений: n/a

Задача о рюкзаке вам в помощь.
  #7  
Старый 19.04.2010, 02:26
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Задача о рюкзаке вам в помощь.
это из другой оперы.

Цитата:
Пасс к логину не помню, стукни в аську
374243274
icq не пользую. и связи между "Пасс к логину не помню" и "стукни в аську" не улавливаю.
  #8  
Старый 19.04.2010, 11:43
Новичок

Отправить личное сообщение для Лили Посмотреть профиль Найти все сообщения от Лили
 
Регистрация: 18.04.2010
Сообщений: 4

Сообщение от гость
ну, перебирай для каждого достоинства монеты, сколько таких монет брать - от 0 до числа монет этого достоинства.
Я понимаю, что нужно перебирать + составлять всевозможные сочетания, но реализовать никак не получается.
  #9  
Старый 19.04.2010, 13:22
гость

 
Сообщений: n/a

а каком языке программирования?
  #10  
Старый 19.04.2010, 13:29
Новичок

Отправить личное сообщение для Лили Посмотреть профиль Найти все сообщения от Лили
 
Регистрация: 18.04.2010
Сообщений: 4

Сообщение от гость
а каком языке программирования?
Delphi
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск кратчайшего пути во взвешенном графе с заданным количеством вершин или ребер Mitrich Графы 9 24.07.2009 18:21
Выпуклая оболочка с фиксированным количеством вершин Belyaev_Igor Вычислительная геометрия 6 16.01.2009 18:45