Diviser le tableau en sous-tableaux à moindre coût en minimisant le nombre d’éléments répétitifs dans chaque sous-tableau

Étant donné un déployer arr[] ayant N entiers de la plage [1, N] et un entier Kla tâche consiste à trouver le coût minimum possible pour diviser le tableau en sous-tableaux non vides qui peut être atteint sur la base des conditions suivantes :

Exemples:

Saisir: arr[] = {1, 2, 3, 1, 2, 3}, K = 2
Production: 4
Explication:
Le fractionnement du tableau en sous-tableaux {1, 2, 3} et {1, 2, 3} génère le coût minimum, car aucun des sous-tableaux ne contient d’élément répétitif.
Toutes les autres divisions coûteront plus cher car un sous-réseau contiendra au moins un élément répétitif.
Par conséquent, le coût minimum possible est de 4.

Saisir: arr[] = {1, 2, 1, 1, 1}, K = 2
Production: 6

Approche naïve : L’idée la plus simple pour résoudre le problème est de générer tous les sous-tableaux possibles pour précalculer et stocker leurs coûts respectifs. Ensuite, calculez le coût de chaque fractionnement possible pouvant être effectué sur la baie. Enfin, imprimez le coût minimum de toutes les divisions.
Suivez les étapes ci-dessous pour résoudre le problème :

  1. Précalculez le coût de chaque sous-réseau en fonction des conditions ci-dessus.
  2. Générez toutes les divisions possibles pouvant être effectuées sur la baie.
  3. Pour chaque division, calculez le coût total de chaque sous-réseau de séparateurs.
  4. Continuez à maintenir le coût total minimum généré et enfin, imprimez la somme minimum.

Complexité temporelle : SUR!)
Espace Auxiliaire : SUR)

Approche efficace : L’idée est d’utiliser Programmation dynamique pour optimiser l’approche ci-dessus. Suivez les étapes ci-dessous pour résoudre le problème :

  1. Initialiser un tableau dp[] de longueur N avec INT_MAX à tous les indices.
  2. Initialiser le premier élément du tableau avec zéro.
  3. Pour tout indice je le tableau dp[i] représente le coût minimum pour diviser le tableau en sous-tableaux à partir de 0 à je.
  4. Pour chaque indice jecompter le coût minimum pour tous les indices de je à N.
  5. Répétez ce processus pour tous les éléments du tableau
  6. Renvoie les derniers éléments de dp[] pour obtenir le coût minimum de fractionnement du tableau.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int findMinCost(vector<int>& a, int k)

{

    

    int n = (int)a.size();

    

    int max_ele = *max_element(a.begin(),

                               a.end());

    

    

    ll dp[n + 1];

    

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

        dp[i] = INT_MAX;

    

    dp[0] = 0;

    for (int i = 0; i < n; ++i) {

        

        int freq[max_ele + 1];

        

        memset(freq, 0, sizeof freq);

        for (int j = i; j < n; ++j) {

            

            freq[a[j]]++;

            int cost = 0;

            

            

            for (int x = 0;

                 x <= max_ele; ++x) {

                cost += (freq[x] == 1)

                            ? 0

                            : freq[x];

            }

            

            

            dp[j + 1] = min(dp[i] + cost + k,

                            dp[j + 1]);

        }

    }

    

    return dp[n];

}

int main()

{

    vector<int> arr = { 1, 2, 1, 1, 1 };

    

    int K = 2;

    

    cout << findMinCost(arr, K);

    return 0;

}

Java

import java.util.*;

class GFG {

static long findMinCost(int[] a,

                        int k, int n)

{

  

  int max_ele = Arrays.stream(a).max().getAsInt();

  

  

  long[] dp = new long[n + 1];

  

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

    dp[i] = Integer.MAX_VALUE;

  

  dp[0] = 0;

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

  {

    

    int[] freq = new int[max_ele + 1];

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

    {

      

      freq[a[j]]++;

      int cost = 0;

      

      

      for (int x = 0; x <= max_ele; ++x)

      {

        cost += (freq[x] == 1) ? 0 :

                 freq[x];

      }

      

      

      dp[j + 1] = Math.min(dp[i] + coût + k,

                           dp[j + 1]);

    }

  }

  

  return dp[n];

}

public static void main(String[] args)

{

  int[] arr = {1, 2, 1, 1, 1};

  

  int K = 2;

  int n = arr.length;

  

  

  System.out.print(findMinCost(arr,

                               K, n));

}

}

Python3

import sys

def findMinCost(a, k, n):

    

    

    max_ele = max(a)

    

    

    dp = [0] * (n + 1)

    

    for i in range(1, n + 1):

        dp[i] = sys.maxsize

    

    dp[0] = 0

    for i in range(0, n):

        

        

        freq = [0] * (max_ele + 1)

        for j in range(i, n):

            

            

            freq[a[j]] += 1

            cost = 0

            

            

            for x in range(0, max_ele + 1):

                cost += (0 if (freq[x] == 1) else

                               freq[x])

            

            

            dp[j + 1] = min(dp[i] + cost + k,

                            dp[j + 1])

    

    return dp[n]

if __name__ == '__main__':

    

    arr = [ 1, 2, 1, 1, 1 ];

    

    K = 2;

    n = len(arr);

    

    print(findMinCost(arr, K, n));

C#

using System;

using System.Linq;

class GFG{

static long findMinCost(int[] a,

                        int k, int n)

{

  

  int max_ele = a.Max();

  

  

  long[] dp = new long[n + 1];

  

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

    dp[i] = int.MaxValue;

  

  dp[0] = 0;

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

  {

    

    int[] freq = new int[max_ele + 1];

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

    {

      

      freq[a[j]]++;

      int cost = 0;

      

      

      for (int x = 0; x <= max_ele; ++x)

      {

        cost += (freq[x] == 1) ? 0 :

                 freq[x];

      }

      

      

      dp[j + 1] = Math.Min(dp[i] + cost + k,

                           dp[j + 1]);

    }

  }

  

  return dp[n];

}

public static void Main(String[] args)

{

  int[] arr = {1, 2, 1, 1, 1};

  

  int K = 2;

  int n = arr.Length;

  

  

  Console.Write(findMinCost(arr,

                               K, n));

}

}

Javascript

<script>

function findMinCost(a, k)

{

    

    

    var n = a.length;

    

    var max_ele = a.reduce((a, b) => Math.max(a, b))

    

    

    var dp = Array(n + 1).fill(1000000000);

    

    dp[0] = 0;

    for(var i = 0; i < n; ++i)

    {

        

        

        var freq = Array(max_ele + 1).fill(0);

        for(var j = i; j < n; ++j)

        {

            

            

            freq[a[j]]++;

            var cost = 0;

            

            

            for(var x = 0; x <= max_ele; ++x)

            {

                cost += (freq[x] == 1) ? 0 : freq[x];

            }

            

            

            dp[j + 1] = Math.min(dp[i] + cost + k,

                                 dp[j + 1]);

        }

    }

    

    return dp[n];

}

var arr = [ 1, 2, 1, 1, 1 ];

var K = 2;

document.write(findMinCost(arr, K));

</script>

Complexité temporelle : SUR3), où N est la taille du tableau donné.
Espace Auxiliaire : SUR)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut