Наименьшая денежная сумма, которую можно получить, используя только монеты указанного достоинства, превышающие пороговое значение

Question

Другими словами, дан набор из n натуральных чисел A и порог BЯ хочу найти самый маленький C чтобы:

• C > B
• C = A[1] * k[1] + A[2] * k[2] + ... + A[n] * k[n], k[i] целые числа>= 0

В качестве примера, если A = { 6, 11, 16 } тогда значения, которые мы можем получить: { 0, 6, 11, 12, 16, 17, 18, 22, 23, 24, 27, 28, 29, 30, 32 ... } так что если B = 14 затем C было бы 16, B = 22 => C = 23, B = 18 => C = 22

Эта проблема получила следующие ограничения: 2 < n < 50000 < A[i] < 50000 а также 1 < B < 10^9 (вот почему я застрял). Также вам пришлось рассчитывать на массив B размера < 1000 массив C (но это может не иметь значения). И алгоритм должен работать менее чем за 0,3 секунды в C++.

Алгоритм, подобный описанному здесь, решает его, но он недостаточно быстр: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
Я рассчитываю таблицу до B + Amin, потому что Amin * k <= B <= Amin * ( k + 1 ) <= B + Amin
Вот алгоритм (в псевдо C++):

int n, A[n], B;
int Amin; // smallest number from A

// table[i] will tell us if it is possible or not to obtain the number i
bool table[B + Amin];
table[0] = true;
for( int i = 0; i < n; ++i )
{
    int x = A[i]; // current number / denomination
    for( int j = x; j <= B + Amin; ++j )
        if( table[j - x] ) 
            table[j] = true;
}

// now we can do something like this:
int result = B + 1;
while( !table[result] ) 
    ++result;

Этот алгоритм имеет сложность O(n*B) и я ищу что-то, что не зависит от B (или, может быть, имеет O(log(B)) или же O(sqrt(B)))

Примечание: если мы сделаем первое требование C >= B тогда проблема не изменится (просто добавьте +1 к B), и мы можем спросить это следующим образом: если у нас есть конкретные монеты или банкноты (бесконечные из них) и мы хотим купить что-то с ними, то какую сумму мы можем платить так, чтобы кассир должен был вернуть минимальные изменения.

---

Вещи, которые я подозреваю, могут помочь:
https://en.wikipedia.org/wiki/Coin_problem
Если самый большой общий делитель ( x, y ) = 1 тогда что-нибудь выше, чем xy − x − y можно получить с помощью x а также y,

http://https//en.wikipedia.org/wiki/Extended_Euclidean_algorithm

https://en.wikipedia.org/wiki/Subset_sum_problem

---

Редактировать: добавлен пример и примечание.

Answer 1

Я не думаю, что вы можете стать лучше, чем O(n*B), потому что число Фробениуса (выше этого числа все суммы могут быть построены с заданными номиналами) 49999 и 49998 2499750005 намного больше, чем 10^9, и вы Необходимо рассчитать наилучшее значение хотя бы для некоторых входов. Если gcd(A) > 1, то число Фробениуса не существует, но этого можно избежать, поделив все A и B (округление вниз) на gcd (A) и умножив C, полученное вами, на gcd (A), чтобы получить конечный результат.

В вашем псевдокоде еще много возможностей для улучшения. Вы смотрите на все деноминации почти раз B+Amin, а также несколько раз устанавливаете значение в таблице на true.

Стандартная реализация будет выглядеть примерно так:

sort(A);
table[0] = true;
for (int i = A[0]; i <= B + A[0]; i++)
    for (int j = 0; j < n && A[j] <= i; j++)
        if (table[i - A[j]]) {
            table[i] = true;
            break;
        }

Это уже немного лучше (обратите внимание на перерыв). Я называю это обратной реализацией, потому что вы оглядываетесь со всех позиций в таблице, чтобы увидеть, можете ли вы найти значение, которое имеет разность одного из заданных номиналов. Вы также можете ввести в таблицу счетчик для числа последовательных значений, для которых установлено значение true (увеличить счетчик, если для значения в таблице установлено значение true, сбросить, если значение не удалось построить, вернуть B+1, если counter == A[0] - 1).

Возможно, вы могли бы даже получить лучшие результаты с помощью прямой реализации, потому что таблица может быть очень разреженной, здесь ложные значения таблицы пропускаются вместо наименований:

table[0] = true;
for (int i = 0; i <= B + Amin; i++)
    if (table[i])
        for (j = 0; j < n; j++)
            if (i + A[j] <= B + Amin)
                table[i + A[j]] = true;