Найдите минимальную сумму, такую, чтобы был взят один из каждых трех последовательных элементов

31.12.2019Динамическое программирование, Массивы

Учитывая массив из n неотрицательных чисел, задача состоит в том, чтобы найти минимальную сумму элементов (выбранных из массива), чтобы по крайней мере один элемент выбирался из каждых 3 последовательных элементов в массиве.

Примеры :

Input : arr[] = {1, 2, 3}
Output : 1

Input : arr[] = {1, 2, 3, 6, 7, 1}
Output : 4
We pick 3 and 1  (3 + 1 = 4)
Note that there are following subarrays
of three consecutive elements
{1, 2, 3}, {2, 3, 6}, {3, 6, 7} and {6, 7, 1}
We have picked one element from every subarray.

Input : arr[] = {1, 2, 3, 6, 7, 1, 8, 6, 2,
                 7, 7, 1}
Output : 7
The result is obtained as sum of 3 + 1 + 2 + 1

Пусть sum (i) будет минимально возможной суммой, когда arr [i] является частью суммы решения (не обязательно является результатом) и является последним выбранным элементом. Тогда наш результат — минимум суммы (n-1), суммы (n-2) и суммы (n-3) [Мы должны выбрать хотя бы один из трех последних элементов].
Мы можем рекурсивно вычислить сумму (i) как сумму arr [i] и минимума (сумма (i-1), сумма (i-2), сумма (i-3)). Поскольку в рекурсивной структуре задачи есть перекрывающиеся подзадачи , мы можем использовать динамическое программирование для решения этой проблемы.

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

C ++

// Программа C ++ на основе динамического программирования для
// найти минимально возможную сумму элементов массива
// такой, что элемент из каждых трех
// выбран подряд
#include <iostream>

using namespace std;

// Функция полезности, чтобы найти минимум
// 3 элемента

int minimum(int a, int b, int c)

{

return min(min(a, b), c);

}

// Возвращает минимально возможную сумму элементов, таких
// что элемент из каждых трех последовательных
// элементы выбраны.

int findMinSum(int arr[], int n)

{

// Создать таблицу DP для хранения результатов

// подзадачи. сумма [я] собирается хранить

// минимально возможная сумма, когда arr [i]

// часть решения.

int sum[n];

// Когда есть меньше или равно

// 3 элемента

sum[0] = arr[0];

sum[1] = arr[1];

sum[2] = arr[2];

// перебираем все остальные элементы

for (int i=3; i<n; i++)

sum[i] = arr[i] +

minimum(sum[i-3], sum[i-2], sum[i-1]);

return minimum(sum[n-1], sum[n-2], sum[n-3]);

}

// Код драйвера

int main()

{

int arr[] = {1, 2, 3, 20, 2, 10, 1};

int n = sizeof(arr)/sizeof(arr[0]);

cout << "Min Sum is " << findMinSum(arr, n);

return 0;

}

Джава

// Java-программа на основе динамического программирования для
// найти минимально возможную сумму элементов массива
// такой, что элемент из каждых трех
// выбран подряд

import java.io.*;

class GFG

{

// Функция полезности, чтобы найти минимум

// 3 элемента

static int minimum(int a, int b, int c)

{

return Math. min(Math.min(a, b), c);

}

// Возвращает минимально возможную сумму элементов, таких

// что элемент из каждых трех последовательных

// элементы выбраны.

static int findMinSum(int arr[], int n)

{

// Создать таблицу DP для хранения результатов

// подзадачи. сумма [я] собирается хранить

// минимально возможная сумма, когда arr [i]

// часть решения.

int sum[] =new int[n];

// Когда есть меньше или равно

// 3 элемента

sum[0] = arr[0];

sum[1] = arr[1];

sum[2] = arr[2];

// перебираем все остальные элементы

for (int i = 3; i < n; i++)

sum[i] = arr[i] + minimum(sum[i - 3],

sum[i - 2], sum[i - 1]);

return minimum(sum[n - 1], sum[n - 2], sum[n - 3]);

}

// Код драйвера

public static void main (String[] args)

{

int arr[] = {1, 2, 3, 20, 2, 10, 1};

int n = arr.length;

System.out.println("Min Sum is " + findMinSum(arr, n));

}

// Этот код предоставлен vt_m

python3

# Программа Python 3 на основе динамического программирования для
# найти минимально возможную сумму элементов массива
# такой, что элемент из каждых трех
# подряд выбран

# Функция полезности, чтобы найти минимум
# 3 элемента

def minimum(a, b, c):

return min(min(a, b), c);

# Возвращает минимально возможную сумму элементов, таких
# что элемент из каждых трех последовательных
# элементов выбрано.

def findMinSum(arr,n):

# Создать таблицу DP для хранения результатов

# подзадачи. сумма [я] собирается хранить

# минимально возможная сумма, когда arr [i]

# часть решения.

sum = []

# Когда есть меньше или равно

# 3 элемента

sum.append(arr[0])

sum.append(arr[1])

sum.append(arr[2])

# Перебирать все остальные элементы

for i in range(3, n):

sum.append( arr[i] + minimum(sum[i-3],

sum[i-2], sum[i-1]))

return minimum(sum[n-1], sum[n-2], sum[n-3])

# Код драйвера

arr = [1, 2, 3, 20, 2, 10, 1]

n = len(arr)

print( "Min Sum is ",findMinSum(arr, n))

# Этот код предоставлен Sam007

C #

// Программа C # на основе динамического программирования для
// найти минимально возможную сумму элементов массива
// такой, что элемент из каждых трех
// выбран подряд

using System;

class GFG

{

// Функция полезности, чтобы найти минимум

// 3 элемента

static int minimum(int a, int b, int c)

{

return Math. Min(Math.Min(a, b), c);

}

// Возвращает минимально возможную сумму элементов, таких

// что элемент из каждых трех последовательных

// элементы выбраны.

static int findMinSum(int []arr, int n)

{

// Создать таблицу DP для хранения результатов

// подзадачи. сумма [я] собирается хранить

// минимально возможная сумма, когда arr [i]

// часть решения.

int []sum =new int[n];

// Когда есть меньше или равно

// 3 элемента

sum[0] = arr[0];

sum[1] = arr[1];

sum[2] = arr[2];

// перебираем все остальные элементы

for (int i = 3; i < n; i++)

sum[i] = arr[i] + minimum(sum[i - 3],

sum[i - 2], sum[i - 1]);

return minimum(sum[n - 1], sum[n - 2], sum[n - 3]);

}

// Код драйвера

public static void Main ()

{

int []arr = {1, 2, 3, 20, 2, 10, 1};

int n = arr.Length;

Console.WriteLine("Min Sum is " + findMinSum(arr, n));

}

// Этот код предоставлен Sam007

PHP

<?php
// Динамическое программирование на основе
// PHP программа для поиска минимума
// возможная сумма элементов
// массив такой, что элемент
// из каждых трех последовательных
// выбрано.

// функция для поиска минимума
// 3 элемента

function minimum($a, $b, $c)

{

return min(min($a, $b), $c);

}

// Возвращает минимально возможную сумму
// элементов, таких что
// элемент из каждых трех
// последовательные элементы выбраны.

function findMinSum($arr, $n)

{

// Создать таблицу DP для хранения результатов

// подзадачи. сумма [я] собирается хранить

// минимально возможная сумма, когда arr [i]

// часть решения.

$sum[$n] = 0;

// когда есть меньше

// чем или равно

// 3 элемента

$sum[0] = $arr[0];

$sum[1] = $arr[1];

$sum[2] = $arr[2];

// перебираем все остальные элементы

for ($i = 3; $i < $n; $i++)

$sum[$i] = $arr[$i] + minimum($sum[$i - 3],

$sum[$i - 2], $sum[$i - 1]);

return minimum($sum[$n - 1], $sum[$n - 2],

$sum[$n - 3]);

}

// Код драйвера

$arr = array(1, 2, 3, 20, 2, 10, 1);

$n = sizeof($arr);

echo "Min Sum is " , findMinSum($arr, $n);

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

Выход:

Min Sum is 4

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Эта проблема и решение внесены Аюшем Салуджей . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найдите минимальную сумму, такую, чтобы был взят один из каждых трех последовательных элементов

0.00 (0%) 0 votes