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

Question

[NQUARE]

Здравствуйте!
Подскажите плиз как определить все способы выплаты суммы n с помощью монет достоинством в 1, 5, 10, 15, 20, 50 копеек, n вводится с клавиатуры, а числа 1, 5, 10, 15, 20, 50 хронатся в массиве. Делал алгоритм, но он работал не совсем правильно, выдавал только способы с одинаковыми числами.
Заранее спасибо!)

Answer 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;
}

Answer 2

[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];
}

Comments

[NQUARE]

Ух уж этот рюкзак. А через статическое как?

[Wataru]

NQUARE, В смысле статическое? Типа, антоним к "динамическое программирование"? Погуглите "динамическое программирование", что ли?

Тут есть всего 2 решения: полный перебор или то, что я привел выше. Я думаю, что это задание как раз и идет в курсе, где вам про динамическое программирование рассказывали и его и хотят увидеть.

[NQUARE]

Нет ни какого курса, ни кто мне ни чего не рассказывал и ни кто ни что не хочет увидеть.
Я в этом не особо шарю, Я имел ввиду как ваш алгоритм сделать под обычный массив а не вектор?

[Wataru]

NQUARE, А, ну дак заведите массив (лучше глобальный тогда) размера так, чтобы максимально возможный n поместился.

const int kMaxN = 100000;
int count[kMaxN+1];
int Count(int n)
...

Но не забудьте, если массив локальный или вы несколько раз вычисляете для разных n, обнулять массив в начале.

[NQUARE]

Можете полный код скинуть?

[NQUARE]

А, и ещё забыл сказать, надо что бы не количество вариантов выводило, а их самих.

[Wataru]

NQUARE, А, ну раз варианты нужны - пишите полный перебор.

[NQUARE]

Можт подскажите как это сделать?\

[Wataru]

NQUARE,

Перебор с максимальных монет до минимальных, потому что так быстрее - не перебираются тупиковые ветки ( ведь всегда можно взять монету веса 1). Массив coins перед вызовом перебора надо отсортировать.

// Входные данные - монеты.
int coints[100];
int num_coins;

// Данные перебора - сколько каждой монеты взяли.
int taken[100];

// Параметры - сколько осталось разменять
// и какую самую большую монету еще можно брать. 
void Generate(int left, int max_coin_idx) {
  if (left == 0) {
    // Вывод текущего размена.
    for (int c = 0; c < num_coins; ++c) {
      for (int i = 0; i < taken[c];++i) {
        printf("%d ", coins[c]);
      }
    } 
    printf("\n");
    return;
  }
  if (max_coin_idx < 0) return;
  for (int cur = 0; cur*coins[max_coin_idx] <= left; ++cur) {
    taken[max_coin_idx] = cur;
    Generate(left - cur*coins[max_coin_idx], max_coin_idx-1);
  }
  // Важно! Отчистить глобальный массив от мусора.
  // другая ветка рекурсии может найти размен не дойдя 
  // до этой монеты.
  taken[max_coin_idx] = 0;
  return;
}

// Вызов перебора.
Generate(n, num_coins-1);