Partición de un conjunto en K subconjuntos con igual suma usando BitMask y DP

Dada una array de enteros arr[] que consta de N enteros, la tarea es verificar si es posible dividir la array dada en K subconjuntos no vacíos de igual suma, de modo que cada elemento de la array sea parte de un solo subconjunto.
Ejemplos: 
 

Entrada: arr[] = {2, 1, 4, 5, 6}, K = 3 
Salida: Sí 
Explicación: 
Los subconjuntos posibles de la array dada son {2, 4}, (1, 5} y {6}
Entrada: arr [] = {2, 1, 5, 5, 6}, K = 3 
Salida: No 
 

Para el enfoque recursivo, consulte Partición de un conjunto en K subconjuntos con igual suma .
Enfoque: 
siga los pasos a continuación para resolver el problema: 
 

  • La idea es usar máscara para determinar el estado actual. El estado actual nos dirá sobre el subconjunto ya formado (qué números ya están seleccionados). 
    Por ejemplo: arr[] = [2, 1, 4, 3, 5, 6, 2], mask = (1100101), lo que significa que { 2, 1, 5, 2 } ya están seleccionados en la máscara actual.
  • Para cualquier máscara de estado actual, se le agregará  el j -ésimo elemento en función de las dos condiciones siguientes:
     
  1. El j -ésimo bit no está configurado en la máscara ( máscara&(1<<j) == 0 )
  2. sum (máscara) + arr[j] <= target (donde target = (Suma de los elementos de la array) / K)
  • Mantenga una tabla dp[] tal que dp[i] almacene la suma de elementos en la máscara i . Entonces, las transiciones dp serán:
     

dp[yo | (1 << j)] = (dp[i] + arr[j]) % objetivo 
Ilustración: 
arr [ ] = [4, 3, 2, 3, 5, 2, 1], K = 4, tar = 5 
dp[“1100101”] implica que se eligen { 4, 3, 5, 1 }  Por lo
tanto, Sum = 4 + 3 + 5 + 1 = 13, 13 % 5 = 3. 
Por lo tanto, dp[“1100101”] = 3
Si dp[“11111…1111”] == 0 entonces eso significa que podemos encontrar la solución. 
 

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

C++

// C++ program to check if the
// given array can be partitioned
// into K subsets with equal sum
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether
// K required partitions
// are possible or not
bool isKPartitionPossible(int arr[],
                          int N, int K)
{
    if (K == 1)
        // Return true as the
        // entire array is the
        // answer
        return true;
 
    // If total number of
    // partitions exceeds
    // size of the array
    if (N < K)
        return false;
 
    int sum = 0;
    for (int i = 0; i < N; i++)
        sum += arr[i];
    // If the array sum is not
    // divisible by K
    if (sum % K != 0)
        // No such partitions are
        // possible
        return false;
 
    // Required sum of
    // each subset
    int target = sum / K;
 
    // Initialize dp array with -1
    int dp[(1 << 15)];
    for (int i = 0; i < (1 << N); i++)
        dp[i] = -1;
 
    // Sum of empty subset
    // is zero
    dp[0] = 0;
 
    // Iterate over all subsets/masks
    for (int mask = 0; mask < (1 << N); mask++) {
        // if current mask is invalid, continue
        if (dp[mask] == -1)
            continue;
 
        // Iterate over all array elements
        for (int i = 0; i < N; i++) {
            // Check if the current element
            // can be added to the current
            // subset/mask
            if (!(mask & (1 << i))
                && dp[mask]
                           + arr[i]
                       <= target) {
                // transition
                dp[mask | (1 << i)]
                    = (dp[mask]
                       + arr[i])
                      % target;
            }
        }
    }
 
    if (dp[(1 << N) - 1] == 0)
        return true;
    else
        return false;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 1, 4, 5, 3, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
 
    if (isKPartitionPossible(arr, N, K)) {
        cout << "Partitions into equal ";
        cout << "sum is possible.\n";
    }
    else {
        cout << "Partitions into equal ";
        cout << "sum is not possible.\n";
    }
}

Java

// Java program to check if the
// given array can be partitioned
// into K subsets with equal sum
import java.util.*;
 
class GFG{
 
// Function to check whether
// K required partitions
// are possible or not
static boolean isKPartitionPossible(int arr[],
                                    int N, int K)
{
    if (K == 1)
     
        // Return true as the
        // entire array is the
        // answer
        return true;
 
    // If total number of
    // partitions exceeds
    // size of the array
    if (N < K)
        return false;
 
    int sum = 0;
    for(int i = 0; i < N; i++)
       sum += arr[i];
        
    // If the array sum is not
    // divisible by K
    if (sum % K != 0)
     
        // No such partitions are
        // possible
        return false;
 
    // Required sum of
    // each subset
    int target = sum / K;
 
    // Initialize dp array with -1
    int []dp = new int[(1 << 15)];
    for(int i = 0; i < (1 << N); i++)
       dp[i] = -1;
 
    // Sum of empty subset
    // is zero
    dp[0] = 0;
 
    // Iterate over all subsets/masks
    for(int mask = 0; mask < (1 << N); mask++)
    {
        
       // if current mask is invalid, continue
       if (dp[mask] == -1)
           continue;
        
       // Iterate over all array elements
       for(int i = 0; i < N; i++)
       {
           
          // Check if the current element
          // can be added to the current
          // subset/mask
          if (((mask & (1 << i)) == 0) &&
             dp[mask] + arr[i] <= target)
          {
               
              // Transition
              dp[mask | (1 << i)] = (dp[mask] +
                                      arr[i]) %
                                      target;
          }
       }
    }
 
    if (dp[(1 << N) - 1] == 0)
        return true;
    else
        return false;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 2, 1, 4, 5, 3, 3 };
    int N = arr.length;
    int K = 3;
 
    if (isKPartitionPossible(arr, N, K))
    {
        System.out.print("Partitions into equal ");
        System.out.print("sum is possible.\n");
    }
    else
    {
        System.out.print("Partitions into equal ");
        System.out.print("sum is not possible.\n");
    }
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program to check if the
# given array can be partitioned
# into K subsets with equal sum
 
# Function to check whether
# K required partitions
# are possible or not
def isKPartitionPossible(arr, N, K):
     
    if (K == 1):
         
        # Return true as the
        # entire array is the
        # answer
        return True
 
    # If total number of
    # partitions exceeds
    # size of the array
    if (N < K):
        return False
 
    sum = 0
    for i in range(N):
        sum += arr[i]
         
    # If the array sum is not
    # divisible by K
    if (sum % K != 0):
         
        # No such partitions are
        # possible
        return False
 
    # Required sum of
    # each subset
    target = sum / K
 
    # Initialize dp array with -1
    dp = [0 for i in range(1 << 15)]
    for i in range((1 << N)):
        dp[i] = -1
 
    # Sum of empty subset
    # is zero
    dp[0] = 0
 
    # Iterate over all subsets/masks
    for mask in range((1 << N)):
         
        # If current mask is invalid,
        # continue
        if (dp[mask] == -1):
            continue
 
        # Iterate over all array elements
        for i in range(N):
             
            # Check if the current element
            # can be added to the current
            # subset/mask
            if ((mask & (1 << i) == 0) and
              dp[mask] + arr[i] <= target):
                 
                # Transition
                dp[mask | (1 << i)] = ((dp[mask] +
                                        arr[i]) %
                                        target)
 
    if (dp[(1 << N) - 1] == 0):
        return True
    else:
        return False
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 2, 1, 4, 5, 3, 3 ]
    N = len(arr)
    K = 3
 
    if (isKPartitionPossible(arr, N, K)):
        print("Partitions into equal "\
              "sum is possible.")
    else:
        print("Partitions into equal sum "\
              "is not possible.")
 
# This code is contributed by Surendra_Gangwar

C#

// C# program to check if the
// given array can be partitioned
// into K subsets with equal sum
using System;
 
class GFG{
 
// Function to check whether
// K required partitions
// are possible or not
static bool isKPartitionPossible(int []arr,
                                 int N, int K)
{
    if (K == 1)
         
        // Return true as the
        // entire array is the
        // answer
        return true;
 
    // If total number of
    // partitions exceeds
    // size of the array
    if (N < K)
        return false;
 
    int sum = 0;
    for(int i = 0; i < N; i++)
       sum += arr[i];
         
    // If the array sum is not
    // divisible by K
    if (sum % K != 0)
     
        // No such partitions are
        // possible
        return false;
 
    // Required sum of
    // each subset
    int target = sum / K;
 
    // Initialize dp array with -1
    int []dp = new int[(1 << 15)];
    for(int i = 0; i < (1 << N); i++)
       dp[i] = -1;
 
    // Sum of empty subset
    // is zero
    dp[0] = 0;
 
    // Iterate over all subsets/masks
    for(int mask = 0; mask < (1 << N); mask++)
    {
        
       // If current mask is invalid, continue
       if (dp[mask] == -1)
           continue;
        
       // Iterate over all array elements
       for(int i = 0; i < N; i++)
       {
            
          // Check if the current element
          // can be added to the current
          // subset/mask
          if (((mask & (1 << i)) == 0) &&
             dp[mask] + arr[i] <= target)
          {
               
              // Transition
              dp[mask | (1 << i)] = (dp[mask] +
                                      arr[i]) %
                                      target;
          }
       }
    }
 
    if (dp[(1 << N) - 1] == 0)
        return true;
    else
        return false;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 2, 1, 4, 5, 3, 3 };
    int N = arr.Length;
    int K = 3;
 
    if (isKPartitionPossible(arr, N, K))
    {
        Console.Write("Partitions into equal ");
        Console.Write("sum is possible.\n");
    }
    else
    {
        Console.Write("Partitions into equal ");
        Console.Write("sum is not possible.\n");
    }
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program to check if the
// given array can be partitioned
// into K subsets with equal sum
 
// Function to check whether
// K required partitions
// are possible or not
function isKPartitionPossible(arr, N, K)
{
    if (K == 1)
       
        // Return true as the
        // entire array is the
        // answer
        return true;
   
    // If total number of
    // partitions exceeds
    // size of the array
    if (N < K)
        return false;
   
    let sum = 0;
    for(let i = 0; i < N; i++)
       sum += arr[i];
          
    // If the array sum is not
    // divisible by K
    if (sum % K != 0)
       
        // No such partitions are
        // possible
        return false;
   
    // Required sum of
    // each subset
    let target = sum / K;
   
    // Initialize dp array with -1
    let dp = Array.from({length: (1 << 15)}, (_, i) => 0);
    for(let i = 0; i < (1 << N); i++)
       dp[i] = -1;
   
    // Sum of empty subset
    // is zero
    dp[0] = 0;
   
    // Iterate over all subsets/masks
    for(let mask = 0; mask < (1 << N); mask++)
    {
          
       // if current mask is invalid, continue
       if (dp[mask] == -1)
           continue;
          
       // Iterate over all array elements
       for(let i = 0; i < N; i++)
       {
             
          // Check if the current element
          // can be added to the current
          // subset/mask
          if (((mask & (1 << i)) == 0) &&
             dp[mask] + arr[i] <= target)
          {
                 
              // Transition
              dp[mask | (1 << i)] = (dp[mask] +
                                      arr[i]) %
                                      target;
          }
       }
    }
   
    if (dp[(1 << N) - 1] == 0)
        return true;
    else
        return false;
}
 
// Driver Code
 
    let arr = [ 2, 1, 4, 5, 3, 3 ];
    let N = arr.length;
    let K = 3;
   
    if (isKPartitionPossible(arr, N, K))
    {
        document.write("Partitions into equal ");
        document.write("sum is possible.\n");
    }
    else
    {
        document.write("Partitions into equal ");
        document.write("sum is not possible.\n");
    }
             
</script>

Producción:  

Partitions into equal sum is possible.

Complejidad Temporal: O (N * 2 N )  
Espacio Auxiliar: O (2 N )
 

Publicación traducida automáticamente

Artículo escrito por rahulrawat09 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 *