Набрать сумму наименьшим количеством чисел из заданного набора

Эта задача и ей подобные - одна из самых популярных на собеседованиях. Не помню, решал ли я здесь такую (вижу только варианты получения суммы из комбинации заданных слагаемых), давайте решим сейчас в самой типовой постановке.

Имеется значение 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 [2228 просмотров]