Имеем на входе массив из положительных чисел, необходимо привести сумму массива к нулю. Для этого есть на входе две переменные. Первая переменная позволяет обнулить элемент массива, вторая - преобразует элемент массива со знаком "-". Необходим алгоритм поиска наименее затратного преобразования массива. Пример:
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).
Какой алгоритм можно применить к такому случаю? Я рассматриваю А*, но не могу никак его приспособить к массиву. Может кто то знает более изящное решение?
y=5
это стоимость одной смены знака,x=2
это стоимость обнуления. надо решить задачу минимизацииN*y + M*x => min
, гдеN,M
- число обнулений и смен знаков, при которых сумма массива станет равной нулю