Рубрики

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

Учитывая массив из 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