@NQUARE

Как определить все способы выплаты суммы n с помощью монет достоинством в 1, 5, 10, 15, 20, 50 копеек?

Здравствуйте!
Подскажите плиз как определить все способы выплаты суммы n с помощью монет достоинством в 1, 5, 10, 15, 20, 50 копеек, n вводится с клавиатуры, а числа 1, 5, 10, 15, 20, 50 хронатся в массиве. Делал алгоритм, но он работал не совсем правильно, выдавал только способы с одинаковыми числами.
Заранее спасибо!)
  • Вопрос задан
  • 136 просмотров
Решения вопроса 1
@NQUARE Автор вопроса
#include <iostream>
#include <string>

using namespace std;
 
int cs[] = {1, 2, 5, 10, 50, 100, 200, 500, 1000, 2000, 5000}, s;
 
void f(int sq, int i, string v) {
    if (sq == 0) cout << v << "\n"; 
    else if (sq > 0 && i >= 0) {
        f(sq - cs[i], i, v + (v == "" ? " " : "+") + to_string(cs[i])); 
        f(sq, i - 1, v);
    }
}
 
int main() { 
	cin >> s;
	f(s, sizeof(cs)/sizeof(cs[0]) - 1, "");
	return 0;
}
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru
Это задача о рюкзаке.

Решение через динамическое программирование:
int Count(vector<int> coins, int n) {
  vector<int> cnt(n+1, 0);
  cnt[0] = 1;
  for (int i = 0; i < n; ++i) {
    for (int coin : coins) {
      if (i+coin <= n) cnt[i+coin] += cnt[i];
    }
  }
  return cnt[n];
}
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы