Проверьте, может ли целое число быть представлено как линейная комбинация целых чисел в массиве

Question

Я пытаюсь решить проблему, в которой задано целое число n и массив целых чисел a - можно n представить в виде линейной комбинации элементов из a так, чтобы коэффициенты положительные целые числа.

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

int gcd(int a, int b) {
  if (a == 0) {
    return b;
  }
  return gcd(b % a, a);
}

bool can_be_changed(const int a[], int len, int val) {
  for (int i = 0; i < len - 1; i++) {
    for (int j = i + 1; j < len; j++) {
      if (val % gcd(a[i], a[j]) == 0) {
        return true;
      }
    }
  }
  return false;
}

Но, если a = {4,5,6} и val=7, код вернет true как gcd(4,5) = 1, а 7 % gcd(4,5) == 0 будет иметь значение true, возвращая, таким образом, trueчто не должно.

Любая помощь приветствуется, спасибо!

Answer 1

TL; DR: здесь самый простой алгоритм , наиболее эффективный алгоритм описан ниже.

Когда вы ограничиваете коэффициенты положительными целыми числами, эта проблема является NP-полной (если len является частью ввода и не является фиксированной). Так что по-настоящему эффективного решения не произойдет. (Она называется «Проблема неограниченной суммы подмножеств», если вы хотите погуглить; доказательство ее сложности здесь .)

Самый эффективный алгоритм, который я нашел, взят из этой статьи :

Операция 10 _t представляет собой «ограниченную сумму», также описанную в статье: в основном она работает следующим образом (набросок в Python):

def capped_sumset(a, b, t): # a, b sets of naturals, t natural
    a0 = a | {0}
    b0 = b | {0}
    return {
        x+y
            for x in a0
            for y in b0
        if x+y <= t
    }

Самым сложным в реализации этого в C будут все операции над множествами; если у вас есть хорошая реализация наборов целых чисел, сам алгоритм не так уж плох.

Если вы не заботитесь об эффективности, конечно, вы можете использовать «классическую динамическую программу», упомянутую в базовом случае алгоритма; подробное объяснение с примерами на нескольких языках программирования можно найти здесь . Но будьте готовы к экспоненциальному времени бега!