Оптимізація пошуку мінімальної суми для рівняння

6 Березня 2024 в 00:14 43

Запит на знаходження мінімальної суми для рівняння за заданим набором обмежень може бути ефективніше оптимізований. За введеним алгоритмом часова складність становить O(n^4 * Z_MAX^2), що може бути неприйнятно великою при значних значеннях n та Z_MAX. Одним із способів зменшення часової складності є використання підходу, який дозволяє знаходити розв’язок без перебору всіх можливих комбінацій a і b.

Замість перебору всіх можливих значень a і b можна скористатися властивостями математичного рівняння a*x + b*y = z. Зауважимо, що якщо знаємо значення змінних x і y, то можемо знайти a і b шляхом ділення z на x або y з урахуванням цілочисельного ділення. Таким чином, замість перебору всіх значень a і b, ми можемо знаходити відповідні значення a і b відразу.

Перепишемо функцію solve, використовуючи цей підхід:

public static int[] solveOptimized(int[] arr, int[] zArr, int Z_MAX) {
    int n = arr.length;
    int[] result = new int[zArr.length];
    for(int i = 0; i < zArr.length; i++) {
        result[i] = Integer.MAX_VALUE;
    }
    
    for(int p = 0; p < zArr.length; p++) {
        int z = zArr[p];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int x = arr[i];
                int y = arr[j];
                
                if(x != 0 && z % x == 0) {
                    int a = z / x;
                    int b = (z - a * x) / y;
                    if(b * y + a * x == z && a + b <= Z_MAX) {
                        result[p] = Math.min(result[p], a + b);
                    }
                }
                
                if(y != 0 && z % y == 0) {
                    int b = z / y;
                    int a = (z - b * y) / x;
                    if(a * x + b * y == z && a + b <= Z_MAX) {
                        result[p] = Math.min(result[p], a + b);
                    }
                }
            }
        }
        if(result[p] > Z_MAX) {
            result[p] = -1;
        }
    }
    
    return result;
}