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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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