Dada una array arr[] que consta de N enteros positivos y un entero positivo K , la tarea es encontrar la diferencia mínima entre la suma de los elementos presentes en dos subconjuntos de tamaño K , de modo que cada elemento de la array pueda aparecer como máximo en 1 subconjunto .
Ejemplos:
Entrada: arr[] = {12, 3, 5, 6, 7, 17}, K = 2
Salida: 1
Explicación: Considerando dos subconjuntos {5, 6} y {3, 7}, la diferencia entre su suma = ( 5 + 6) – (3 + 7) = (11 – 10) = 1, que es el mínimo posible.Entrada: arr[] = {10, 10, 10, 10, 10, 2}, K = 3
Salida: 8
Explicación: Considerando dos subconjuntos {10, 10, 10} y {10, 10, 2}, la diferencia entre su suma = (10 + 10 + 10) – (10 + 10 + 2) = (30 – 22) = 8.
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subconjuntos posibles de tamaño K y elegir cada par de subconjuntos de tamaño K de manera que cada elemento de la array pueda ocurrir como máximo en 1 subconjunto. Después de encontrar todos los pares de subconjuntos posibles, imprima la diferencia mínima entre la suma de elementos para cada par de subconjuntos.
Complejidad de Tiempo: O(3 N )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Para implementar este enfoque, la idea es usar 3D-array , digamos dp[][][] , para almacenar los estados de cada llamada recursiva .
Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar, digamos dp[][][] , donde dp[i][S1][S2] almacena la suma de los dos subconjuntos formados hasta cada i -ésimo índice .
- Declare una función recursiva , digamos minimalDifference(arr, N, K1, K2, S1, S2) , que acepte una array, el tamaño actual de la array, la cantidad de elementos almacenados en los subconjuntos (K1 y K2) y la suma de elementos en cada subconjunto como parámetros.
- Caso base: si el número de elementos en la array es N y el valor de K1 y K2 es 0 , devuelve la diferencia absoluta entre S1 y S2 .
- Si el resultado del estado actual ya se calculó, devuelva el resultado.
- Almacene el valor devuelto al incluir el N -ésimo elemento en el primer subconjunto y llame recursivamente a las siguientes iteraciones como mínimaDiferencia(arr, N – 1, K1 – 1, K2, S1 + arr[N – 1], S2) .
- Almacene el valor devuelto al incluir el N -ésimo elemento en el primer subconjunto y llame recursivamente a las siguientes iteraciones como minimalDifference(arr, N – 1, K1, K2 – 1, S1, S2 + arr[N – 1]) .
- Almacene el valor devuelto al no incluir el N -ésimo elemento en ninguno de los subconjuntos y llame recursivamente a las siguientes iteraciones como minimalDifference(arr, N – 1, K1, K2, S1, S2) .
- Almacene el mínimo de todos los valores devueltos por las tres llamadas recursivas anteriores en el estado actual, es decir, dp[N][S1][S2] , y devuelva su valor.
- Después de completar los pasos anteriores, imprima el valor devuelto por la función minimalDifference(arr, N, K, K, 0, 0) .
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;
// Stores the values at recursive states
int dp[100][100][100];
// Function to find the minimum difference
// between sum of two K-length subsets
int minSumDifference(int* arr, int n,
int k1, int k2,
int sum1, int sum2)
{
// Base Case
if (n < 0) {
// If k1 and k2 are 0, then
// return the absolute difference
// between sum1 and sum2
if (k1 == 0 && k2 == 0) {
return abs(sum1 - sum2);
}
// Otherwise, return INT_MAX
else {
return INT_MAX;
}
}
// If the result is already
// computed, return the result
if (dp[n][sum1][sum2] != -1) {
return dp[n][sum1][sum2];
}
// Store the 3 options
int op1 = INT_MAX;
int op2 = INT_MAX;
int op3 = INT_MAX;
// Including the element in first subset
if (k1 > 0) {
op1 = minSumDifference(arr, n - 1,
k1 - 1, k2,
sum1 + arr[n],
sum2);
}
// Including the element in second subset
if (k2 > 0) {
op2 = minSumDifference(arr, n - 1,
k1, k2 - 1, sum1,
sum2 + arr[n]);
}
// Not including the current element
// in both the subsets
op3 = minSumDifference(arr, n - 1,
k1, k2,
sum1, sum2);
// Store minimum of 3 values obtained
dp[n][sum1][sum2] = min(op1,
min(op2,
op3));
// Return the value for
// the current states
return dp[n][sum1][sum2];
}
// Driver Code
int main()
{
int arr[] = { 12, 3, 5, 6, 7, 17 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
memset(dp, -1, sizeof(dp));
cout << minSumDifference(arr, N - 1,
K, K, 0, 0);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Stores the values at recursive states
static int[][][] dp = new int[100][100][100];
// Function to find the minimum difference
// between sum of two K-length subsets
static int minSumDifference(int[] arr, int n,
int k1, int k2,
int sum1, int sum2)
{
// Base Case
if (n < 0)
{
// If k1 and k2 are 0, then
// return the absolute difference
// between sum1 and sum2
if (k1 == 0 && k2 == 0)
{
return Math.abs(sum1 - sum2);
}
// Otherwise, return INT_MAX
else
{
return Integer.MAX_VALUE;
}
}
// If the result is already
// computed, return the result
if (dp[n][sum1][sum2] != -1)
{
return dp[n][sum1][sum2];
}
// Store the 3 options
int op1 = Integer.MAX_VALUE;
int op2 = Integer.MAX_VALUE;
int op3 = Integer.MAX_VALUE;
// Including the element in first subset
if (k1 > 0)
{
op1 = minSumDifference(arr, n - 1,
k1 - 1, k2,
sum1 + arr[n],
sum2);
}
// Including the element in second subset
if (k2 > 0)
{
op2 = minSumDifference(arr, n - 1,
k1, k2 - 1, sum1,
sum2 + arr[n]);
}
// Not including the current element
// in both the subsets
op3 = minSumDifference(arr, n - 1,
k1, k2,
sum1, sum2);
// Store minimum of 3 values obtained
dp[n][sum1][sum2] = Math.min(op1,
Math.min(op2, op3));
// Return the value for
// the current states
return dp[n][sum1][sum2];
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 12, 3, 5, 6, 7, 17 };
int K = 2;
int N = arr.length;
for(int[][] row:dp)
{
for(int[] innerrow : row)
{
Arrays.fill(innerrow,-1);
}
}
System.out.println(minSumDifference(arr, N - 1, K,
K, 0, 0));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program for the above approach import sys # Stores the values at recursive states dp = [[[ -1 for i in range(100)] for i in range(100)] for i in range(100)] # Function to find the minimum difference # between sum of two K-length subsets def minSumDifference(arr, n, k1, k2, sum1, sum2): global dp # Base Case if (n < 0): # If k1 and k2 are 0, then # return the absolute difference # between sum1 and sum2 if (k1 == 0 and k2 == 0): return abs(sum1 - sum2) # Otherwise, return INT_MAX else: return sys.maxsize + 1 # If the result is already # computed, return the result if (dp[n][sum1][sum2] != -1): return dp[n][sum1][sum2] # Store the 3 options op1 = sys.maxsize + 1 op2 = sys.maxsize + 1 op3 = sys.maxsize + 1 # Including the element in first subset if (k1 > 0): op1 = minSumDifference(arr, n - 1, k1 - 1, k2, sum1 + arr[n], sum2) # Including the element in second subset if (k2 > 0): op2 = minSumDifference(arr, n - 1, k1, k2 - 1, sum1, sum2 + arr[n]) # Not including the current element # in both the subsets op3 = minSumDifference(arr, n - 1, k1, k2, sum1, sum2) # Store minimum of 3 values obtained dp[n][sum1][sum2] = min(op1, min(op2, op3)) # Return the value for # the current states return dp[n][sum1][sum2] # Driver Code if __name__ == '__main__': arr = [12, 3, 5, 6, 7, 17] K = 2 N = len(arr) #memset(dp, -1, sizeof(dp)) print (minSumDifference(arr, N - 1, K, K, 0, 0)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Stores the values at recursive states
static int[,,] dp = new int[100, 100, 100];
// Function to find the minimum difference
// between sum of two K-length subsets
static int minSumDifference(int[] arr, int n,
int k1, int k2,
int sum1, int sum2)
{
// Base Case
if (n < 0)
{
// If k1 and k2 are 0, then
// return the absolute difference
// between sum1 and sum2
if (k1 == 0 && k2 == 0)
{
return Math.Abs(sum1 - sum2);
}
// Otherwise, return INT_MAX
else
{
return Int32.MaxValue;
}
}
// If the result is already
// computed, return the result
if (dp[n, sum1, sum2] != -1)
{
return dp[n, sum1, sum2];
}
// Store the 3 options
int op1 = Int32.MaxValue;
int op2 = Int32.MaxValue;
int op3 = Int32.MaxValue;
// Including the element in first subset
if (k1 > 0)
{
op1 = minSumDifference(arr, n - 1,
k1 - 1, k2,
sum1 + arr[n],
sum2);
}
// Including the element in second subset
if (k2 > 0)
{
op2 = minSumDifference(arr, n - 1,
k1, k2 - 1, sum1,
sum2 + arr[n]);
}
// Not including the current element
// in both the subsets
op3 = minSumDifference(arr, n - 1,
k1, k2,
sum1, sum2);
// Store minimum of 3 values obtained
dp[n, sum1, sum2] = Math.Min(op1,
Math.Min(op2, op3));
// Return the value for
// the current states
return dp[n, sum1, sum2];
}
// Driver Code
static public void Main()
{
int[] arr = { 12, 3, 5, 6, 7, 17 };
int K = 2;
int N = arr.Length;
for(int i = 0; i < 100; i++)
{
for(int j = 0; j < 100; j++)
{
for(int k = 0; k < 100; k++)
{
dp[i, j, k] = -1;
}
}
}
Console.WriteLine(minSumDifference(arr, N - 1, K,
K, 0, 0));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program for the above approach
// Stores the values at recursive states
let dp = new Array(100);
for(let i = 0; i < 100; i++)
{
dp[i] = new Array(100);
for(let j = 0; j < 100; j++)
{
dp[i][j] = new Array(100);
for(let k = 0; k < 100; k++)
dp[i][j][k] = -1;
}
}
// Function to find the minimum difference
// between sum of two K-length subsets
function minSumDifference(arr, n, k1, k2, sum1, sum2)
{
// Base Case
if (n < 0)
{
// If k1 and k2 are 0, then
// return the absolute difference
// between sum1 and sum2
if (k1 == 0 && k2 == 0)
{
return Math.abs(sum1 - sum2);
}
// Otherwise, return INT_MAX
else
{
return Number.MAX_VALUE;
}
}
// If the result is already
// computed, return the result
if (dp[n][sum1][sum2] != -1)
{
return dp[n][sum1][sum2];
}
// Store the 3 options
let op1 = Number.MAX_VALUE;
let op2 = Number.MAX_VALUE;
let op3 = Number.MAX_VALUE;
// Including the element in first subset
if (k1 > 0)
{
op1 = minSumDifference(arr, n - 1,
k1 - 1, k2,
sum1 + arr[n],
sum2);
}
// Including the element in second subset
if (k2 > 0)
{
op2 = minSumDifference(arr, n - 1,
k1, k2 - 1, sum1,
sum2 + arr[n]);
}
// Not including the current element
// in both the subsets
op3 = minSumDifference(arr, n - 1,
k1, k2,
sum1, sum2);
// Store minimum of 3 values obtained
dp[n][sum1][sum2] = Math.min(op1,
Math.min(op2, op3));
// Return the value for
// the current states
return dp[n][sum1][sum2];
}
// Driver Code
let arr = [12, 3, 5, 6, 7, 17 ];
let K = 2;
let N = arr.length;
document.write(minSumDifference(arr, N - 1, K,
K, 0, 0));
// This code is contributed by patel2127
</script>
Producción:
1
Complejidad de tiempo: O(N*S 2 ), donde S es la suma de los elementos de la array dada
Espacio auxiliar: O(N*S 2 )
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA