Набрать сумму наименьшим количеством чисел из заданного набора
Эта задача и ей подобные - одна из самых популярных на собеседованиях. Не помню, решал ли я здесь такую (вижу только варианты получения суммы из комбинации заданных слагаемых), давайте решим сейчас в самой типовой постановке.
Имеется значение V
(рублей, долларов и т.п.) и набор монет с достоинствами D
, выраженными в тех же единицах, например, { 1, 2, 5, 10, 20, 50, 100, 500, 1000 }
.
Количество монет любого достоинства не ограничено. Нужно набрать сумму V
наименьшим возможным количеством монет.
В простейшем случае мы можем, найдя наибольшее достоинство монеты, не превышающее V
, добавить его к итоговой сумме, а затем вычитать эту сумму из V
. Далее процесс повторяется для нового значения V
, вот что примерно выходит (консоль Visual Studio 2015):
#include <iostream> #include <vector> using namespace std; int main() { int V = 999; int D[] = { 1, 2, 5, 10, 20, 50, 100, 500, 1000 }; int n = sizeof(D) / sizeof(D[0]); cout << "V=" << V << ": "; vector <int> summa; for (int i = n - 1; i > -1; i--) { while (V >= D[i]) { V -= D[i]; summa.push_back(D[i]); } } int size = summa.size(); for (int i = 0; i < size; i++) cout << summa[i] << " "; cout << endl << "Count of coins = " << size; cin.get(); return 0; }
V=999: 500 100 100 100 100 50 20 20 5 2 2 Count of coins = 11
Можно, конечно, решать и с рекурсивной функцией, и методами динамического программирования, но едва ли решения окажутся проще, особенно если мы хотим не только определить количество монет, но и показать их набор.
04.04.2019, 14:01 [2229 просмотров]