0

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

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).

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

4
  • Не понятно из условия каким образом происходит обнуление и смена знака. Также укажите пожалуйста как вы считаете стоимость.
    – becouse
    23 июн 2020 в 22:09
  • Почему в первом примере стоимость 5, хотя изменен только знак у одного числа?
    – becouse
    23 июн 2020 в 22:10
  • @becouse y=5 это стоимость одной смены знака, x=2 это стоимость обнуления. надо решить задачу минимизации N*y + M*x => min, где N,M - число обнулений и смен знаков, при которых сумма массива станет равной нулю
    – teran
    23 июн 2020 в 22:23
  • Книга Томаса Кормена "Алгоритмы. Вводный курс", глава 7 "Алгоритмы на строках", раздел "Преобразование одной строки в другую" - по-моему, очень похоже на вашу задачу. 24 июн 2020 в 0:18

1 ответ 1

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 при ненулевой сумме на выходе - если не получилось занулить данной последовательностью, возвращаем заведомо большое число...

0

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.