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