Пусть найдется некоторое положительное целое число Z и пусть будет список N неотрицательных целых чисел, обозначенных z0 ... zn-1. Каков алгоритм, который может найти наименьшее кратное Z, которое может выражаются через сумму всех zi * ci, где ci - любая неотрицательная целочисленная константа?Алгоритм: Найти наименьшее количество
Этот алгоритм должен выполняться во времени O (Z * (N + log (Z))).
Я попытался решить эту проблему с помощью алгоритма djikstras и дошел до определения того, что для выполнения требования временной сложности должны быть края Z * N и Z вершины. Я также выяснил, что каждый ni может иметь не более Z разных коэффициентов, поскольку (min zi)/zi * Z связан Z.
Возможно, есть какой-то способ сделать это, исследуя установку циклического графика?
Что такое ni? В постановке задачи упоминаются только Z, N, zi и ci. –
Также я предполагаю, что ваш zi начинается с i = 1, а не i = 0, в противном случае из них N + 1. –
И что ваши ci ограничены целыми числами, так как в противном случае проблема тривиальна. –