Форум программистов, компьютерный форум CyberForum.ru

Минимальное количество монет - C++

Восстановить пароль Регистрация
 
Дед Мороз
0 / 0 / 0
Регистрация: 26.12.2010
Сообщений: 4
11.12.2011, 16:10     Минимальное количество монет #1
Есть такая задача:
Денежная система некоторой страны предоставляет монеты номиналом с, = 1, с2, ..., сN. Как выдать сумму S с помощью минимального числа монет?
Вход. В первой строке — сумма S и количество номиналов N, во второй — значения номиналов: 1<N≤20, 1=с1<с2<...< сN≤50000, S≤100000.
Выход. В первой строке — минимальное количество монет, во второй — N чисел (количества монет каждого номинала).
Понимаю как должна работать программа. А вот как начать реализовывать не могу понять. Кто знает подкиньте идеии. Можно через рекурсию или динамическое программирование.

Добавлено через 21 час 36 минут
подскажите с чего начать. Просто не могу понять с чего начинать писать. Организовал ввод и стараюсь понять как писать сам код. Но не получается.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2011, 16:10     Минимальное количество монет
Посмотрите здесь:

C++ можно ли составить данное количество денег, используя только две из данных монет
Удалить символы из строки за минимальное количество ходов. C++
C++ Минимальное количество белых слонов
C++ Найти минимальное количество пересадок между двумя городами
Вывести минимальное количество C++
C++ Определить количество, минимальное и максимальное из введенных чисел
C++ В каждом столбце обнулить минимальное количество элементов
C++ Определить количество различных комбинаций монет, которые могут сложиться в определенную сумму

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 17:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru