Dada una array arr[] de tamaño N y un número entero K , la tarea es minimizar la suma de la diferencia entre el elemento máximo y mínimo de cada subconjunto dividiendo la array en K subconjuntos de modo que cada subconjunto consista únicamente en elementos de array únicos.
Ejemplos:
Entrada: arr[] = { 6, 3, 8, 1, 3, 1, 2, 2 }, K = 4
Salida: 6
Explicación:
una de las formas óptimas de dividir la array en K(= 4) subconjuntos es { { 1, 2 }, { 2, 3 }, { 6, 8 }, { 1, 4 } }.
Suma de la diferencia del elemento máximo y mínimo presente en cada subconjunto = { (2 – 1) + (3 – 2) + (8 – 6) + (3 – 1) } = 6.
Por lo tanto, la salida requerida es 6Entrada: arr[] = { 2, 2, 1, 1 }, K = 1
Salida: -1
Enfoque: El problema se puede resolver usando Programación Dinámica con enmascaramiento de bits . Las siguientes son las relaciones de recurrencia:
máscara: el i -ésimo bit de máscara comprueba si el elemento de la array ya está seleccionado en un subconjunto o no.
l: índice del último elemento seleccionado en un subconjunto.
j: índice del elemento actual seleccionado en un subconjunto.Si el recuento de bits establecidos en máscara mod (N / K) == 1:
dp[máscara][l] = min(dp[máscara][l], dp[máscara ^ (1 << l)][j])De lo contrario,
dp[máscara][j] = min(dp[máscara][j], dp[máscara ^ (1 << j)][l] + nums[l] – nums[j])
Siga los pasos a continuación para resolver el problema:
- Iterar sobre todos los valores posibles de mask , es decir, [0, 2 N – 1]
- Inicialice una array, digamos n_z_bits[] , para almacenar el recuento de elementos ya seleccionados en subconjuntos.
- Use la relación de recurrencia anterior y complete todos los estados dp posibles de la relación de recurrencia.
- Finalmente, imprima los elementos mínimos de dp[(1 << N ) – 1] .
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program to implement
# the above approach
from itertools import permutations
from itertools import combinations
# Function to minimize the sum of
# difference between maximums and
# minimums of K subsets of an array
def MinimizeSum(nums, k):
# Stores count of elements
# in an array
n = len(nums)
# Base Case
if k == n:
return 0
# Initialize DP[][] array
dp = [[float("inf")] * n for _ in range(1 << n)]
# Sort the array
nums.sort()
# Mark i-th element
# as not selected
for i in range(n):
dp[1 << i][i] = 0
# Iterate over all possible
# values of mask
for mask in range(1 << n):
# Store count of set bits
# in mask
n_z_bits = []
# Store index of element which is
# already selected in a subset
for p, c in enumerate(bin(mask)):
if c == "1":
temp = len(bin(mask)) - p - 1
n_z_bits.append(temp)
# If count of set bits in mask
# mod (n // k) equal to 1
if len(n_z_bits) % (n//k) == 1:
for j, l in permutations(n_z_bits, 2):
temp = dp[mask ^ (1 << l)][j]
dp[mask][l] = min(dp[mask][l], temp)
else:
for j, l in combinations(n_z_bits, 2):
if nums[j] != nums[l]:
# Check if l-th element
# is already selected or not
mask_t = mask ^ (1 << l)
temp = (dp[mask_t][j] +
nums[j] - nums[l])
# Update dp[mask][l]
dp[mask][l] = min(dp[mask][l],
temp)
# Return minimum element
# from dp[(1 << N) - 1]
if min(dp[-1]) != float("inf"):
return min(dp[-1])
# If dp[-1] is inf then the
# partition is not possible
else:
return -1
# Driver Code
if __name__ == "__main__":
# Given array
arr = [ 6, 3, 8, 1, 3, 1, 2, 2 ]
K = 4
# Function call
print(MinimizeSum(arr, K))
6
Complejidad de Tiempo: O(N* 2 N )
Espacio Auxiliar: O(N * 2 N )
Publicación traducida automáticamente
Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA