Как проверить, является ли целое число суммированных чисел?

Question

Скажем, у меня есть целое число result и массив целых чисел, скажем [a,b,c] (не фиксированная длина). Мне нужно определить, result=a*i +b*j + c*k, с i,j,k>=0.

Я предпочитаю решение в C/C#, если это возможно.

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

Спасибо!

Ex: если у нас есть = 3, Ь = 7 чем rezult 20 = 3 * 2 + 7 * 2 результат 9 = 3 * 3 + 7 * 0

Answer 1

Ваша проблема утверждение слишком расплывчатой будьте уверены - каковы возможные значения i, j, k ... если входной вектор не является фиксированной длиной?

Это звучит для меня, как будто ваша проблема является вариацией на knapsack problem.

Answer 2

Это Frobenius Problem, который находится в общей NP-Hard.

Для небольших случаев известны достаточно быстрые алгоритмы.

Документ здесь: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf, как представляется, описывает предыдущие алгоритмы (включая приложение алгоритма кратчайшего пути Dijkstra!), Плюс он дает новый алгоритм, который, по-видимому, быстрее предыдущих.

В любом случае для случая, когда имеется только 2 числа, a и b такие, что gcd (a, b) = 1, найдя i, j> 0, так что a i + b j = M легко решить.

Известно также, что любое число, большее, чем (а-1) (б-1) может быть представлена ​​в виде а I + б J с I> = 0 и J> = 0. Число Фробениуса определяется как наибольшее число, которое невозможно представить в этой форме и существует, когда n> = 2 и gcd (a, b, c ...) = 1.

Так что в вашем случае, если используемые числа достаточно малы, вы можете отсортировать массив, найти «самые маленькие» два a и b, такие как gcd (a, b) = 1 и посмотреть, есть ли M> (a-1) (b-1), что может решаются только с помощью a и b.

если M < = (a-1) (b-1), а a и b являются достаточно маленькими, вы можете просто выполнить команду перебора.