Minimizar la suma de incompatibilidades de K subconjuntos de igual longitud formados por elementos únicos

Dada una array arr[] que consta de N enteros y un entero K, la tarea es encontrar la suma mínima de incompatibilidades de K subconjuntos de igual tamaño que tienen elementos únicos.

La diferencia entre el elemento máximo y mínimo de un conjunto se conoce como incompatibilidad de un conjunto .

Ejemplos: 

Entrada: arr[] = {1, 2, 1, 4}, K = 2
Salida: 4
Explicación: 
una de las formas posibles de distribuir la array en K (es decir, 2) subconjuntos es {1, 2} y {1 , 4}.
La incompatibilidad del primer subconjunto = (2 – 1) = 1.
La incompatibilidad del segundo subconjunto = (4 – 1) = 3.
Por tanto, la suma total de incompatibilidades de ambos subconjuntos = 1 + 3 = 4, que es la mínimo entre todas las posibilidades.

Entrada: arr[] = {6, 3, 8, 1, 3, 1, 2, 2}, K = 4
Salida: 6
Explicación: 
una de las formas posibles de distribuir la array en K subconjunto es: {1, 2 }, {2, 3}, {6, 8}, {1, 3}.
La incompatibilidad del primer subconjunto = (2-1) = 1.
La incompatibilidad del segundo subconjunto = (3-2) = 1.
La incompatibilidad del tercer subconjunto = (8-6) = 2.
La incompatibilidad del cuarto subconjunto = (3-1) = 2.
Por lo tanto, suma total de incompatibilidades de K subconjunto = 1 + 1 + 2 + 2 = 6. Y también es el mínimo entre todas las posibilidades 

Enfoque ingenuo: el enfoque más simple es recorrer la array dada de forma recursiva y, en cada recursión, recorrer todas las formas posibles de seleccionar N/K elementos de la array utilizando una máscara de bits y calcular la incompatibilidad de ese subconjunto y luego devolver el mínimo entre todos.

Complejidad de Tiempo: O(N*2 3*N )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar mediante programación dinámica. El problema planteado se puede resolver con base en las siguientes observaciones:

  • Se puede observar que requiere una programación dinámica de 2 estados con Bitmasking, digamos DP (máscara, i) para resolver el problema donde i representa la posición actual de la array y cada bit binario de máscara representa si el elemento ya ha sido seleccionado o no .
  • El estado de transición incluirá el cálculo de la incompatibilidad seleccionando un subconjunto de tamaño N/K .
    • Suponga que X e Y son el mínimo y el máximo del conjunto actual y newmask es otra variable con valor inicialmente como la máscara
    • Ahora, marque todos los elementos N/ K que se han seleccionado solo una vez en máscara nueva , luego DP (máscara, i) se calcula mediante (Y – X + min (DP (máscara nueva, i + 1), DP (máscara, i) )) .

Siga los pasos a continuación para resolver el problema:

  • Inicialice una array 2D , digamos dp[][] .
  • Defina una función recursiva , digamos dfs (máscara, i) , para calcular el resultado:
    • Caso base: si i > K , devuelve 0 .
    • Compruebe si dp[mask][i] != -1 , luego devuelva dp[mask][i] ya que el estado actual ya está calculado.
    • Seleccione N/K elementos de la array utilizando el enmascaramiento de bits y, si es posible, elija los elementos i del subconjunto que solo aparecen una vez y que aún no forman parte de otros subconjuntos, luego actualice el estado de dp actual como:

dp[máscara][i] = min(dp[máscara][i], Y – X + dfs(nueva máscara, i))

  • Devuelve el valor de dp[mask][i] como resultado de la llamada recursiva actual.
  • Llame a la función recursiva dfs(2 N -1, 0) e imprima el valor que devuelve.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int k;
int n;
int goal;
vector<vector<int>> dp;
vector<int> bits;
 
// Recursive function to find
// the minimum required value
int dfs(vector<int> A, int state,int index)
{
   
    // Base Case
    if (index >= k)
    {
        return 0;
    }
 
    // Stores the minimum value
    // of the current state
    int res = 1000;
 
    // If dp[state][index] is
    // already calculated
    if (dp[state][index] != -1) {
 
        // return dp[state][index]
        return dp[state][index];
    }
 
    // Traverse over all the bits
    for (int bit : bits) {
 
        // If count of set bit is N/K
        if (__builtin_popcount(bit)
            == goal) {
 
            // Store the new state after
            // choosing N/K elements
            int newstate = state;
 
            // Stores the minimum and
            // maximum of current subset
            int mn = 100, mx = -1;
 
            // Stores if the elements
            // have been already
            // selected or not
            vector<bool> visit(n+1,false);
 
            // Stores if it is possible
            // to select N/K elements
            bool good = true;
 
            // Traverse over the array
            for (int j = 0; j < n; j++) {
 
                // If not chosen already
                // for another subset
                if ((bit & (1 << j)) != 0) {
 
                    // If already chosen
                    // for another subset
                    // or current subset
                    if (visit[A[j]] == true
                        || (state & (1 << j)) == 0) {
 
                        // Mark the good false
                        good = false;
                        break;
                    }
 
                    // Mark the current
                    // number visited
                    visit[A[j]] = true;
 
                    // Mark the current
                    // position in mask
                    // newstate
                    newstate = newstate
                               ^ (1 << j);
 
                    // Update the maximum
                    // and minimum
                    mx = max(mx,
                                  A[j]);
                    mn = min(mn,
                                  A[j]);
                }
            }
 
            // If good is true then
            // Update the res
            if (good) {
                res = min(
                    res, mx - mn
                             + dfs(A, newstate,
                                   index + 1));
            }
        }
    }
 
    // Update the current sp state
    dp[state][index] = res;
 
    // Return the res
    return res;
}
 
// Function to find the minimum
// incompatibility sum
int minimumIncompatibility(vector<int> A, int K)
{
    n = A.size();
    k = K;
    goal = n / k;
   
    // Stores the count of element
    map<int, int> mp;
 
    // Traverse the array
    for (int i : A) {
 
        // If number i not occurs
        // in Map
        if (mp.find(i)==mp.end()){
            // Put the element
            // in the Map
            mp[i] = 0;
          }
 
        // Increment the count of
        // i in the Hash Map
        mp[i]++;
 
        // If count of i in Map is
        // greater than K then
        // return -1
        if (mp[i] > k)
            return -1;
    }
 
    // Stores all total state
    int state = (1 << n) - 1;
 
    // Traverse over all the state
    for (int i = 0; i <= state; i++) {
 
        // If number of set bit
        // is equal to N/K
        if (__builtin_popcount(i) == goal){
            bits.push_back(i);
        }
    }
 
    // Stores the minimum value
    // at a state
    dp.resize(1<<n,vector<int>(k,-1));
 
    // Initialize the dp state
    // with -1
    // for (int i = 0;
    //      i < dp.ize(); i++) {
    //     Arrays.fill(dp[i], -1);
    // }
 
    // Call the recursive function
    return dfs(A, state, 0);
}
 
// Driver code
int main()
{
 
    vector<int> arr = { 1, 2, 1, 4 };
    int K = 2;
 
    // Function Call
    cout<<(minimumIncompatibility(arr, K));
}
 
// This code is contributed by mohit kumar 29.

Java

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class Solution {
    int k;
    int n;
    int goal;
    int dp[][];
    List<Integer> bits = new ArrayList<>();
 
    // Function to find the minimum
    // incompatibility sum
    public int minimumIncompatibility(
        int[] A, int k)
    {
        this.n = A.length;
        this.k = k;
        goal = n / k;
 
        // Stores the count of element
        Map<Integer, Integer> map
            = new HashMap<>();
 
        // Traverse the array
        for (int i : A) {
 
            // If number i not occurs
            // in Map
            if (!map.containsKey(i))
 
                // Put the element
                // in the Map
                map.put(i, 0);
 
            // Increment the count of
            // i in the Hash Map
            map.put(i, map.get(i) + 1);
 
            // If count of i in Map is
            // greater than K then
            // return -1
            if (map.get(i) > k)
                return -1;
        }
 
        // Stores all total state
        int state = (1 << n) - 1;
 
        // Traverse over all the state
        for (int i = 0; i <= state; i++) {
 
            // If number of set bit
            // is equal to N/K
            if (Integer.bitCount(i) == goal)
                bits.add(i);
        }
 
        // Stores the minimum value
        // at a state
        dp = new int[1 << n][k];
 
        // Initialize the dp state
        // with -1
        for (int i = 0;
             i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }
 
        // Call the recursive function
        return dfs(A, state, 0);
    }
 
    // Recursive function to find
    // the minimum required value
    public int dfs(int A[], int state,
                   int index)
    {
        // Base Case
        if (index >= k) {
            return 0;
        }
 
        // Stores the minimum value
        // of the current state
        int res = 1000;
 
        // If dp[state][index] is
        // already calculated
        if (dp[state][index] != -1) {
 
            // return dp[state][index]
            return dp[state][index];
        }
 
        // Traverse over all the bits
        for (int bit : bits) {
 
            // If count of set bit is N/K
            if (Integer.bitCount(bit)
                == goal) {
 
                // Store the new state after
                // choosing N/K elements
                int newstate = state;
 
                // Stores the minimum and
                // maximum of current subset
                int mn = 100, mx = -1;
 
                // Stores if the elements
                // have been already
                // selected or not
                boolean visit[]
                    = new boolean[n + 1];
 
                // Stores if it is possible
                // to select N/K elements
                boolean good = true;
 
                // Traverse over the array
                for (int j = 0; j < n; j++) {
 
                    // If not chosen already
                    // for another subset
                    if ((bit & (1 << j)) != 0) {
 
                        // If already chosen
                        // for another subset
                        // or current subset
                        if (visit[A[j]] == true
                            || (state & (1 << j)) == 0) {
 
                            // Mark the good false
                            good = false;
                            break;
                        }
 
                        // Mark the current
                        // number visited
                        visit[A[j]] = true;
 
                        // Mark the current
                        // position in mask
                        // newstate
                        newstate = newstate
                                   ^ (1 << j);
 
                        // Update the maximum
                        // and minimum
                        mx = Math.max(mx,
                                      A[j]);
                        mn = Math.min(mn,
                                      A[j]);
                    }
                }
 
                // If good is true then
                // Update the res
                if (good) {
                    res = Math.min(
                        res, mx - mn
                                 + dfs(A, newstate,
                                       index + 1));
                }
            }
        }
 
        // Update the current sp state
        dp[state][index] = res;
 
        // Return the res
        return res;
    }
}
 
// Driver Code
class GFG {
 
    public static void main(String[] args)
    {
        Solution st = new Solution();
        int[] arr = { 1, 2, 1, 4 };
        int K = 2;
 
        // Function Call
        System.out.print(
            st.minimumIncompatibility(arr, K));
    }
}

Python3

# Python program for the above approach:
 
k = 0
n = 0
goal = 0
dp = []
bits = []
 
def __builtin_popcount(n):
    count = 0
    while (n > 0):
        count += (n & 1)
        n >>= 1
    return count
 
## Recursive function to find
## the minimum required value
def dfs(A, state, index):
 
    global k
    global n
    global goal
    global dp
    global bits
    ## Base Case
    if (index >= k):
        return 0;
 
    ## Stores the minimum value
    ## of the current state
    res = 1000
 
    ## If dp[state][index] is
    ## already calculated
    if (dp[state][index] != -1):
 
        ## return dp[state][index]
        return dp[state][index];
 
    ## Traverse over all the bits
    for bit in bits:
 
        ## If count of set bit is N/K
        if (__builtin_popcount(bit) == goal):
 
            ## Store the new state after
            ## choosing N/K elements
            newstate = state;
 
            ## Stores the minimum and
            ## maximum of current subset
            mn = 100
            mx = -1
 
            ## Stores if the elements
            ## have been already
            ## selected or not
            visit = [False]*(n+1)
 
            ## Stores if it is possible
            ## to select N/K elements
            good = True
 
            ## Traverse over the array
            for j in range(0, n):
 
                ## If not chosen already
                ## for another subset
                if ((bit & (1 << j)) != 0):
 
                    ## If already chosen
                    ## for another subset
                    ## or current subset
                    if (visit[A[j]] == True or (state & (1 << j)) == 0):
 
                        ## Mark the good false
                        good = False;
                        break;
 
                    ## Mark the current
                    ## number visited
                    visit[A[j]] = True;
 
                    ## Mark the current
                    ## position in mask
                    ## newstate
                    newstate = newstate ^ (1 << j);
 
                    ## Update the maximum
                    ## and minimum
                    mx = max(mx, A[j])
                    mn = min(mn, A[j])
 
            ## If good is True then
            ## Update the res
            if (good):
                res = min(res, mx - mn + dfs(A, newstate, index + 1))
 
    ## Update the current sp state
    dp[state][index] = res
 
    ## Return the res
    return res
 
## Function to find the minimum
## incompatibility sum
def minimumIncompatibility(A, K):
 
    global k
    global n
    global goal
    global dp
    global bits
    n = len(A)
    k = K
    goal = n // k
 
    ## Stores the count of element
    mp = {}
 
    ## Traverse the array
    for i in A:
 
        ## If number i not occurs
        ## in Map
        if (i not in mp):
            ## Put the element
            ## in the Map
            mp[i] = 0
 
        ## Increment the count of
        ## i in the Hash Map
        mp[i]+=1
 
        ## If count of i in Map is
        ## greater than K then
        ## return -1
        if (mp[i] > k):
            return -1;
 
    ## Stores all total state
    state = (1 << n) - 1;
 
    ## Traverse over all the state
    for i in range(state + 1):
 
        ## If number of set bit
        ## is equal to N/K
        if (__builtin_popcount(i) == goal):
            bits.append(i)
 
    ## Stores the minimum value
    ## at a state
    for i in range(1 << n):
        dp.append([])
        for j in range(k):
            dp[i].append(-1)
 
    ## Call the recursive function
    return dfs(A, state, 0);
 
## Driver code
if __name__=='__main__':
 
    arr = [ 1, 2, 1, 4 ]
    K = 2
 
    ## Function Call
    print(minimumIncompatibility(arr, K))
 
    # This code is contributed by subhamgoyal2014.

C#

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
class Solution {
  int k;
  int n;
  int goal;
  int [,]dp;
  List<int> bits = new List<int>();
 
  // Function to find the minimum
  // incompatibility sum
  public int minimumIncompatibility(
    int[] A, int k)
  {
    this.n = A.Length;
    this.k = k;
    goal = n / k;
 
    // Stores the count of element
    Dictionary<int,int> map
      = new Dictionary<int,int>();
 
    // Traverse the array
    foreach(int i in A) {
 
      // If number i not occurs
      // in Map
      if (!map.ContainsKey(i))
 
        // Put the element
        // in the Map
        map[i]= 0;
 
      // Increment the count of
      // i in the Hash Map
      map[i]++;
 
      // If count of i in Map is
      // greater than K then
      // return -1
      if (map[i] > k)
        return -1;
    }
 
    // Stores all total state
    int state = (1 << n) - 1;
 
    // Traverse over all the state
    for (int i = 0; i <= state; i++) {
 
      // If number of set bit
      // is equal to N/K
      if (Convert.ToString(i, 2).Count(c => c == '1') == goal)
        bits.Add(i);
    }
 
    // Stores the minimum value
    // at a state
    dp = new int[1 << n,k];
 
    // Initialize the dp state
    // with -1
    for (int i = 0;i < dp.GetLength(0); i++) {
 
      for (int j = 0;j < dp.GetLength(1); j++) {
        dp[i,j]=-1;
      }
 
    }
 
    // Call the recursive function
    return dfs(A, state, 0);
  }
 
  // Recursive function to find
  // the minimum required value
  public int dfs(int []A, int state,
                 int index)
  {
    // Base Case
    if (index >= k) {
      return 0;
    }
 
    // Stores the minimum value
    // of the current state
    int res = 1000;
 
    // If dp[state][index] is
    // already calculated
    if (dp[state,index] != -1) {
 
      // return dp[state][index]
      return dp[state,index];
    }
 
    // Traverse over all the bits
    foreach(int bit in bits) {
 
      // If count of set bit is N/K
      if(Convert.ToString(bit, 2).Count(c => c == '1')== goal) {
 
        // Store the new state after
        // choosing N/K elements
        int newstate = state;
 
        // Stores the minimum and
        // maximum of current subset
        int mn = 100, mx = -1;
 
        // Stores if the elements
        // have been already
        // selected or not
        bool []visit
          = new bool[n + 1];
 
        // Stores if it is possible
        // to select N/K elements
        bool good = true;
 
        // Traverse over the array
        for (int j = 0; j < n; j++) {
 
          // If not chosen already
          // for another subset
          if ((bit & (1 << j)) != 0) {
 
            // If already chosen
            // for another subset
            // or current subset
            if (visit[A[j]] == true
                || (state & (1 << j)) == 0) {
 
              // Mark the good false
              good = false;
              break;
            }
 
            // Mark the current
            // number visited
            visit[A[j]] = true;
 
            // Mark the current
            // position in mask
            // newstate
            newstate = newstate
              ^ (1 << j);
 
            // Update the maximum
            // and minimum
            mx = Math.Max(mx,
                          A[j]);
            mn = Math.Min(mn,
                          A[j]);
          }
        }
 
        // If good is true then
        // Update the res
        if (good) {
          res = Math.Min(
            res, mx - mn
            + dfs(A, newstate,
                  index + 1));
        }
      }
    }
 
    // Update the current sp state
    dp[state,index] = res;
 
    // Return the res
    return res;
  }
}
 
// Driver Code
class GFG {
 
  public static void Main()
  {
    Solution st = new Solution();
    int[] arr = { 1, 2, 1, 4 };
    int K = 2;
 
    // Function Call
    Console.Write(
      st.minimumIncompatibility(arr, K));
  }
}
 
// This code is contributed by rutvik_56.

Javascript

<script>
// Javascript program for the above approach
 
let k,n,goal;
let dp;
let bits = [];
 
// Function to find the minimum
// incompatibility sum
function minimumIncompatibility(A,K)
{
    n = A.length;
    k = K;
    goal = Math.floor(n / k);
     
    // Stores the count of element
        let map = new Map();
  
        // Traverse the array
        for (let i=0;i< A.length;i++) {
  
            // If number i not occurs
            // in Map
            if (!map.has(A[i]))
  
                // Put the element
                // in the Map
                map.set(A[i], 0);
  
            // Increment the count of
            // i in the Hash Map
            map.set(A[i], map.get(A[i]) + 1);
  
            // If count of i in Map is
            // greater than K then
            // return -1
            if (map.get(A[i]) > k)
                return -1;
        }
  
        // Stores all total state
        let state = (1 << n) - 1;
  
        // Traverse over all the state
        for (let i = 0; i <= state; i++) {
  
            // If number of set bit
            // is equal to N/K
            if (i.toString(2).split('0').join('').length == goal)
                bits.push(i);
        }
  
        // Stores the minimum value
        // at a state
        dp = new Array(1 << n);
  
        // Initialize the dp state
        // with -1
        for (let i = 0;
            i < dp.length; i++) {
            dp[i]=new Array(k);
            for(let j=0;j<k;j++)
                dp[i][j]=-1;
        }
  
        // Call the recursive function
        return dfs(A, state, 0);
}
 
// Recursive function to find
// the minimum required value
function dfs(A,state,index)
{
    // Base Case
        if (index >= k) {
            return 0;
        }
  
        // Stores the minimum value
        // of the current state
        let res = 1000;
  
        // If dp[state][index] is
        // already calculated
        if (dp[state][index] != -1) {
  
            // return dp[state][index]
            return dp[state][index];
        }
  
        // Traverse over all the bits
        for (let bit=0;bit< bits.length;bit++) {
  
            // If count of set bit is N/K
            if (bits[bit].toString(2).split('0').join('').length
                == goal) {
  
                // Store the new state after
                // choosing N/K elements
                let newstate = state;
  
                // Stores the minimum and
                // maximum of current subset
                let mn = 100, mx = -1;
  
                // Stores if the elements
                // have been already
                // selected or not
                let visit
                    = new Array(n + 1);
                    for(let i=0;i<=n;i++)
                    {
                        visit[i]=false;
                    }
  
                // Stores if it is possible
                // to select N/K elements
                let good = true;
  
                // Traverse over the array
                for (let j = 0; j < n; j++) {
  
                    // If not chosen already
                    // for another subset
                    if ((bits[bit] & (1 << j)) != 0) {
  
                        // If already chosen
                        // for another subset
                        // or current subset
                        if (visit[A[j]] == true
                            || (state & (1 << j)) == 0) {
  
                            // Mark the good false
                            good = false;
                            break;
                        }
  
                        // Mark the current
                        // number visited
                        visit[A[j]] = true;
  
                        // Mark the current
                        // position in mask
                        // newstate
                        newstate = newstate
                                   ^ (1 << j);
  
                        // Update the maximum
                        // and minimum
                        mx = Math.max(mx,
                                      A[j]);
                        mn = Math.min(mn,
                                      A[j]);
                    }
                }
  
                // If good is true then
                // Update the res
                if (good) {
                    res = Math.min(
                        res, mx - mn
                                 + dfs(A, newstate,
                                       index + 1));
                }
            }
        }
  
        // Update the current sp state
        dp[state][index] = res;
  
        // Return the res
        return res;
}
 
// Driver Code
let arr=[1, 2, 1, 4];
let K = 2;
document.write(minimumIncompatibility(arr, K))
 
 
// This code is contributed by unknown2108
</script>
Producción: 

4

 

Complejidad de Tiempo: O(N 2 *2 2*N )
Espacio Auxiliar: O(N) 

Publicación traducida automáticamente

Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *