Помощь с задачей на рекурсию

Информатика
1

Задача №157. Монетки

Максимальное время работы на одном тесте: 1 секунда

В Волшебной стране используются монетки достоинством A1 , A2 ,…, AM . Волшебный человечек пришел в магазин и обнаружил, что у него есть ровно по две монетки каждого достоинства. Ему нужно заплатить сумму N . Напишите программу, определяющую, сможет ли он расплатиться без сдачи.

Входные данные

На вход программы сначала поступает число N (1 <= N <= 10e9), затем - число M (1 <= M <= 15) и далее M попарно различных чисел A1 , A2 ,…, AM (1 <= Ai <= 10e9).

Выходные данные

Сначала выведите K - количество монет, которое придется отдать Волшебному человечку, если он сможет заплатить указанную сумму без сдачи. Далее выведите K чисел, задающих достоинства монет. Если решений несколько, выведите вариант, в котором Волшебный человек отдаст наименьшее возможное количество монет. Если таких вариантов несколько, выведите любой из них.

Если без сдачи не обойтись, то выведите одно число 0. Если же у Волшебного человечка не хватит денег, чтобы заплатить указанную сумму, выведите одно число -1 (минус один).

Примеры

входные данные

100 6 11 20 30 40 11 99

выходные данные

3 40 30 30
(Вообще не могу решить. Можете разобрать?)
https://informatics.msk.ru/mod/statements/view.php?id=254&chapterid=157#1

2

Решение за O(3^M): переберем все возможные варианты выбора монет, для каждой монеты есть 3 варианта взятия в ответ: 0, 1, или 2.
Используем для этого рекурсивную функцию f(pos, sum), где pos - позиция рассматриваемой монеты, а sum - накопленная сумма к текущему моменту. Изначально мы находимся в состоянии f(0, 0), в конце мы должны оказаться в состоянии f(i, n). На каждом шаге есть три перехода, соответствующие взятию : 0, 1, или 2 монет i-того типа:
f(pos, sum) → f(pos + 1, sum)
f(pos, sum) → f(pos + 1, sum + a[pos])
f(pos, sum) → f(pos + 1, sum + a[pos] * 2)
Запустим каждый из них и соответственно обновим массив ныне выбранных монет cur, и если в шаге f(i, n) видно, что cur улучшает ответ, то сделаем cur новым ответом.

#include <iostream>
#include <vector>
using namespace std;
int n, m, a[20];
long long s;
vector<int> cur, res;
void f(int pos = 0, long long sum = 0) {
  if (pos == m) {
    if (sum == n) {
      if (!res.size() || cur.size() < res.size()) {
        res = cur;
      }
      return;
    }
    return;
  }
  f(pos + 1, sum);
  cur.push_back(a[pos]);
  f(pos + 1, sum + a[pos]);
  cur.push_back(a[pos]);
  f(pos + 1, sum + a[pos] * 2);
  cur.pop_back();
  cur.pop_back();
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a[i];
    s += a[i] * 2;
  }
  if (s < n) {
    cout << -1 << "\n";
    return 0;
  }
  f();
  if (!res.size()) {
    cout << 0 << "\n";
    return 0;
  }
  cout << res.size() << "\n";
  for (auto ans : res) cout << ans << " ";
  return 0;
}
6 лайков
3

а че дешевле нельзя?

p.s. добавил раскраски кода cpp, c, csharp, objectivec

2 лайка
4

можно чета вроде O(2^{(M + 1)})

4 лайка
5

возможно, но вопрос стоит в обучении рекурсии, да и ограничения расчитаны так, чтобы 3^M заходило спокойно

3 лайка
6

Пусть f(mask) = sum_{n=0}^{m - 1} ((\lfloor (mask/2^i) \rfloor mod 2) * A_i), где mask это двоичная маска в десятичной системе счисления.

f(mask_1) + f(mask_2) = N, если мы можем найти такие mask_1 и mask_2, то задача решена.

Давайте заметим что мы можем заранее пройтись по всем mask_1 и добавить в хэш-мапу где ключ будет f(mask_1), а значение это mask_1. Если до этого существовал элемент с ключом f(mask_1) то выбираем ту маску в которой используется минимальное количество монет.

Теперь перебираем mask_2, и проверяем есть ли в хэш мапе ключ N - f(mask_2). Что делать дальше очевидно.

Время : O(2^m)

5 лайков
7

Код на идею за O(2^m):

#include <bits/stdc++.h>
#define pc(x) __builtin_popcount(x)
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define F first
#define S second
using namespace std;
int n, m, a[17], b[1 << 17];
long long s;
unordered_map<int, pair<int, int>> t;
vector<int> res;
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> a[i];
    s += a[i] * 2;
  }
  if (s < n) {
    cout << -1 << "\n";
    return 0;
  }
  for (int i = 0; i < (1 << m); i++) {
    if (i) b[i] = b[i ^ (1 << __lg(i))] + a[__lg(i)];
    if (t.find(b[i]) == t.end())
      t[b[i]] = mp(pc(i), i);
    else
      t[b[i]] = min(t[b[i]], mp(pc(i), i));
  }
  int kek = 60, pos = -1;
  for (int i = 0; i < (1 << m); i++) {
    if (t.find(n - b[i]) != t.end()) {
      if (pc(i) + t[n - b[i]].F < kek) {
        kek = pc(i) + t[n - b[i]].F;
        pos = i;
      }
    }
  }
  if (pos < 0) {
    cout << 0 << "\n";
    return 0;
  }
  for (int i = 0; i < m; i++) {
    if ((1 << i) & pos) res.pb(a[i]);
    if ((1 << i) & t[n - b[pos]].S) res.pb(a[i]);
  }
  cout << res.size() << "\n";
  for (auto ans : res) cout << ans << " ";
  return 0;
}
5 лайков