07.07.2023 10:48
MaxRokatansky 0 927 Источник

Имея массив целых положительных чисел, нужно заменить каждый элемент так, чтобы разница между соседними элементами массива была меньше или равна заданному целевому значению (target). Нам необходимо минимизировать стоимость корректировки, то есть суммарную разницу между новыми и старыми значениями. По сути, нам нужно минимизировать ∑|A[i] — Anew[i]|, где 0 ≤ i ≤ n-1, n — размер A[], а Anew[] — массив с разницей между соседними элементами меньше или равной заданной. Предположим, что все элементы массива меньше константы M = 100.

Примеры:

Вход: arr = [1, 3, 0, 3], target = 1
Выход: Минимальная стоимость корректировки равна 3
Объяснение: Одним из возможных решений 
является [2, 3, 2, 3].

Вход: arr = [2, 3, 2, 3], target = 1
Выход: Минимальная стоимость корректировки равна 0
Пояснение:  Все соседние элементы во входном 
массиве уже меньше, или равны заданной цели

Вход: arr = [55, 77, 52, 61, 39, 6, 
25, 60, 49, 47], target = 10
Выход: Минимальная стоимость корректировки равна 75
Объяснение: Одним из возможных решений является 
[55, 62, 52, 49, 39, 29, 30, 40, 49, 47]

Чтобы минимизировать стоимость корректировки ∑|A[i] - Anew[i]| для всех индексов i в массиве, |A[i] - Anew[i]| должна быть максимально близкой к нулю. Кроме того, |A[i] - Anew[i+1]| ≤ Target.

Данная проблема может быть решена с помощью динамического программирования.

Пусть dp[i][j] определяет минимальные затраты на корректировку при изменении A[i] на j, тогда зависимость DP (Dynamic Programming. Динамическое программирование) определяется следующим образом.

dp[i][j] = min{dp[i - 1][k]} + |j - A[i]|
           для всех k таких, что |k - j| ≤ target

Здесь 0 ≤ i ≤ n и 0 ≤ j ≤ M, где n - количество элементов в массиве, а M = 100. Мы должны рассмотреть все k , которые соответствуют условию max(j - цель, 0) ≤ k ≤ min(M, j + цель). Наконец, минимальная стоимость настройки массива будет min{dp[n - 1][j]} для всех 0 ≤ j ≤ M.

Алгоритм:

  • Создайте двумерный массив с инициализирующим dp[n][M+1] для записи с наименьшей стоимостью корректировки при изменении A[i] на j, где n - длина массива, а M - его максимальное значение.

  • Вычислите наименьшую стоимость изменения A[0] на j для первого элемента массива, dp[0][j], используя формулу dp[0][j] = abs (j - A[0]).

  • Замените A[i] на j в остальных элементах массива, dp[i][j], и используйте формулу dp[i][j] = min(dp[i-1][k] + abs(A[i] - j)), где k принимает все возможные значения между max(j-target,0) и min(M,j+target), чтобы получить минимальную стоимость корректировки.

  • В качестве минимальной стоимости корректировки приводится наименьшее число из последней строки таблицы dp. 

Ниже приведена реализация вышеизложенной идеи:

<?php
// PHP-программа для нахождения минимальной
// стоимости настройки массива

$M = 100;

// Функция для нахождения минимальной
// стоимости настройки массива
function minAdjustmentCost( $A, $n, $target)
{
	
	// dp[i][j] хранит минимальные
	// стоимость корректировки при изменении
	// A[i] на j
	global $M;
	$dp = array(array());

	// обрабатываем первый элемент
	// массива отдельно
	for($j = 0; $j <= $M; $j++)
		$dp[0][$j] = abs($j - $A[0]);

	// делаем для остальных
	// элементов массива
	for($i = 1; $i < $n; $i++)
	{
		
		// заменяем A[i] на j и
		// вычисляем минимальную корректировку
		// стоимость dp[i][j]
		for($j = 0; $j <= $M; $j++)
		{
			
			// инициализируем минимальную корректировку
			// стоимость до INT_MAX
			$dp[$i][$j] = PHP_INT_MAX;
	
			// рассматриваем все k такие, что.
			// k >= max(j - target, 0) и
			// k <= min(M, j + target) и
			// берем минимум
			for($k = max($j - $target, 0);
				$k <= min($M, $j + $target);
									$k++)
				$dp[$i][$j] = min($dp[$i][$j],
							$dp[$i - 1][$k] +
							abs($A[$i] - $j));
		}
	}

	// возвращаем минимальное значение
	// из последней строки таблицы dp
	$res = PHP_INT_MAX;
	for($j = 0; $j <= $M; $j++)
		$res = min($res, $dp[$n - 1][$j]);

	return $res;
}

	// Код драйвера
	$arr = array(55, 77, 52, 61, 39,
				6, 25, 60, 49, 47);
	$n = count($arr);
	$target = 10;

	echo "Минимальная стоимость корректировки составляет "
		, minAdjustmentCost($arr, $n, $target);

// Этот код предоставлен anuj_67.
?>

Вывод:

Минимальная стоимость корректировки составляет 75

Временная сложность: O(n*m2)

Дополнительное пространство: O(n m)

Эффективный подход: оптимизация пространства

В предыдущем подходе текущее значение dp[i][j] зависит только от текущего и предыдущего значений DP. Поэтому при оптимизации сложности пространства мы используем отдельный одномерный массив для хранения вычислений.

Шаги реализации:

  • Создайте одномерный вектор dp размера m+1.

  • Установите базовый случай, инициализировав значения DP.

  • Теперь перебираем подзадачи с помощью вложенного цикла и получаем текущее значение из предыдущих вычислений.

  • Теперь создайте временный вектор 1d prev_dp, используемый для хранения текущих значений от предыдущих вычислений.

  • После каждой итерации присваивайте значение prev_dp вектору dp для дальнейшей обработки.

  • Инициализируйте переменную res для хранения окончательного ответа и обновляйте ее с помощью итераций через Dp.

  • В конце верните и выведите окончательный ответ, хранящийся в res.

Реализация:

#include <bits/stdc++.h>
использование пространства имен std;

#define M 100

// Функция для нахождения минимальной стоимости корректировки массива
int minAdjustmentCost(int A[], int n, int target)
{
	int dp[M + 1]; // Массив для хранения минимальных затрат на корректировку для каждого значения

	for (int j = 0; j <= M; j++)
		dp[j] = abs(j - A[0]); // Инициализация первой строки абсолютными разностями

	for (int i = 1; i < n; i++) // Итерация по элементам массива
	{
		int prev_dp[M + 1];
		memcpy(prev_dp, dp, sizeof(dp)); // Храним минимальные затраты предыдущего ряда

		for (int j = 0; j <= M; j++) // Итерация по возможным значениям
		{
			dp[j] = INT_MAX; // Инициализируем текущее значение максимальной стоимостью

			// Найдите минимальную стоимость, учитывая диапазон предыдущих значений
			for (int k = max(j - target, 0); k <= min(M, j + target); k++)
				dp[j] = min(dp[j], prev_dp[k] + abs(A[i] - j));
		}
	}

	int res = INT_MAX;
	for (int j = 0; j <= M; j++)
		res = min(res, dp[j]); // Находим минимальную стоимость в последней строке

	return res; // Возвращаем минимальную стоимость корректировки
}

int main()
{
	int arr[] = {55, 77, 52, 61, 39, 6, 25, 60, 49, 47};
	int n = sizeof(arr) / sizeof(arr[0]);
	int target = 10;

	cout << "Минимальная стоимость корректировки составляет "
		<< minAdjustmentCost(arr, n, target) << endl;

	return 0;
}

Вывод:

Минимальная стоимость корректировки составляет 75

Временная сложность: O(nm)

Вспомогательное пространство: O(m)

Как написать библиотеку на C или Go для вашего PHP-проекта, а главное — зачем? Обсудим это на открытом уроке 10 июля в 20:00. Занятие посвящено механизму FFI (Foreign Function Interface) в PHP. Поговорим о применении технологии, напишем библиотеку, и добавим ее в проект на PHP. Обсудим случаи применимости технологии FFI, поговорим о том, в каких случаях ее применять не стоит.

Занятие будет полезно для уверенно владеющих PHP разработчиков, которые пришли к вопросу о возможности встраивания низкоуровневых библиотек в свои проекты.

Комментарии (0)