Оптимальный алгоритм для поиска стоимости

Question

Имеем на входе массив из положительных чисел, необходимо привести сумму массива к нулю. Для этого есть на входе две переменные. Первая переменная позволяет обнулить элемент массива, вторая - преобразует элемент массива со знаком "-". Необходим алгоритм поиска наименее затратного преобразования массива. Пример:

int[] array = {1,6,3,2,0}, int x = 2, int y = 5

Оптимальное решение: 1-6+3+2=0, стоимость преобразования 5.

int[] array = {2,2,2,2}, int x = 2, int y = 10

Оптимальное решение: 0+0+0+0, стоимость 8(2*4).

int[] array = {1,5,3,2,0}, int x = 2, int y = 5

Оптимальное решение: 0-5+3+2, стоимость 7(2+5).

Какой алгоритм можно применить к такому случаю? Я рассматриваю А*, но не могу никак его приспособить к массиву. Может кто то знает более изящное решение?

Answer 1

Динамическое программирование. Пример сверху вниз, с мемоизацией (для больших массивов данных):

int zeroing(int * a, int n, int sum = 0, int k = 0)
{
    static map<pair<int,int>,int> m;
    if (k == n)
    {
        return sum ? 6*n : 0;
    }

    if (auto it = m.find(pair<int,int>(sum,k)); it != m.end())
    {
        return it->second;
    }

    int none = zeroing(a,n,sum-a[k],k+1);
    int sign = 5 + zeroing(a,n,sum+a[k],k+1);
    int zero = 2 + zeroing(a,n,sum,k+1);
    int res = min(none,min(sign,zero));
    m.insert(make_pair(pair<int,int>(sum,k),res));
    return res;
}

int main()
{
    int x[] = { 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2 };
    cout << zeroing(x,size(x)) << endl;

}

Для такого размера, как в условии - можно и без нее:

int zeroing(int * a, int n, int sum = 0, int k = 0)
{
    if (k == n) return sum ? 6*n : 0;
    int none = zeroing(a,n,sum-a[k],k+1);
    int sign = 5 + zeroing(a,n,sum+a[k],k+1);
    int zero = 2 + zeroing(a,n,sum,k+1);
    return min(none,min(sign,zero));
}

Если нужно к тому же указывать, что и как менять - сохраняйте заодно результат...

Смысл понятен? Смотрим три варианта действий с очередным элементом, и рекурсивно вычисляем сумму для каждого варианта. Берем минимальную.

Возврат 6*n при ненулевой сумме на выходе - если не получилось занулить данной последовательностью, возвращаем заведомо большое число...

БЛОГ НА HUSL

Оптимальный алгоритм для поиска стоимости

Ответы (1 шт):