Suma máxima del subconjunto tal que no hay dos elementos en el conjunto que tengan el mismo dígito en ellos

Posted on by Rudeus Greyrat

Dada una array de N elementos. Encuentre el subconjunto de elementos que tiene una suma máxima tal que no hay dos elementos en el subconjunto que tengan un dígito común presente en ellos.
Ejemplos:
 

Entrada: array[] = {22, 132, 4, 45, 12, 223} 
Salida: 268 
El subconjunto de suma máxima será = {45, 223}. 
Todos los dígitos posibles están presentes excepto 1.  Pero para incluir 1, se deben eliminar
2 o 2 y 3, lo  que da como resultado un valor de suma más pequeño. Entrada: array[] = {1, 21, 32, 4, 5}  Salida: 42 



 

  • Aquí podemos usar la programación dinámica y el enmascaramiento de bits para resolver esta pregunta.
  • Considere una representación de 10 bits de cada número donde cada bit es 1 si el dígito correspondiente a ese bit está presente en ese número.
  • Ahora mantenga un dp[i], que almacena la suma máxima posible que se puede lograr con todos los dígitos presentes en el conjunto, correspondientes a las posiciones de bit que son 1 en la Representación binaria de i.
  • La relación de recurrencia será de la forma dp[i] = max(dp[i], dp[i^mask] + a[j]) , para todos aquellos j de 1 a n tal que mask (Representación de 10 bits de un [j]) satisface i || máscara = yo. (Desde entonces solo podemos asegurar que todos los dígitos disponibles en i están satisfechos).

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

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
int dp[1024];
  
// Function to create mask for every number
int get_binary(int u)
{
    int ans = 0;
    while (u) {
        int rem = u % 10;
        ans |= (1 << rem);
        u /= 10;
    }
  
    return ans;
}
  
// Recursion for Filling DP array
int recur(int u, int array[], int n)
{
    // Base Condition
    if (u == 0)
        return 0;
    if (dp[u] != -1)
        return dp[u];
  
    int temp = 0;
    for (int i = 0; i < n; i++) {
        int mask = get_binary(array[i]);
  
        // Recurrence Relation
        if ((mask | u) == u) {
            dp[u] = max(max(0,
                    dp[u ^ mask]) + array[i], dp[u]);
        }
    }
  
    return dp[u];
}
  
// Function to find Maximum Subset Sum
int solve(int array[], int n)
{
    // Initialize DP array
    for (int i = 0; i < (1 << 10); i++) {
        dp[i] = -1;
    }
  
    int ans = 0;
  
    // Iterate over all possible masks of 10 bit number
    for (int i = 0; i < (1 << 10); i++) {
        ans = max(ans, recur(i, array, n));
    }
  
    return ans;
}
  
// Driver Code
int main()
{
    int array[] = { 22, 132, 4, 45, 12, 223 };
    int n = sizeof(array) / sizeof(array[0]);
     
    cout << solve(array, n);
}

Java

// Java implementation of above approach
import java.io.*;
 
class GFG
{
     
static int []dp = new int [1024];
 
// Function to create mask for every number
static int get_binary(int u)
{
    int ans = 0;
    while (u > 0)
     
    {
        int rem = u % 10;
        ans |= (1 << rem);
        u /= 10;
    }
 
    return ans;
}
 
// Recursion for Filling DP array
static int recur(int u, int []array, int n)
{
    // Base Condition
    if (u == 0)
        return 0;
    if (dp[u] != -1)
        return dp[u];
 
    for (int i = 0; i < n; i++)
    {
        int mask = get_binary(array[i]);
 
        // Recurrence Relation
        if ((mask | u) == u)
        {
            dp[u] = Math.max(Math.max(0,
                    dp[u ^ mask]) + array[i], dp[u]);
        }
    }
 
    return dp[u];
}
 
// Function to find Maximum Subset Sum
static int solve(int []array, int n)
{
    // Initialize DP array
    for (int i = 0; i < (1 << 10); i++)
    {
        dp[i] = -1;
    }
 
    int ans = 0;
 
    // Iterate over all possible masks of 10 bit number
    for (int i = 0; i < (1 << 10); i++)
    {
        ans = Math.max(ans, recur(i, array, n));
    }
 
    return ans;
}
 
// Driver Code
static public void main (String[] args)
{
    int []array = { 22, 132, 4, 45, 12, 223 };
    int n = array.length;
     
    System.out.println(solve(array, n));
}
}
 
// This code is contributed by anuj_67..

Python3

# Python3 implementation of above approach
 
dp = [0]*1024;
 
# Function to create mask for every number
def get_binary(u) :
 
    ans = 0;
    while (u) :
        rem = u % 10;
        ans |= (1 << rem);
        u //= 10;
    return ans;
 
 
# Recursion for Filling DP array
def recur(u, array, n) :
 
    # Base Condition
    if (u == 0) :
        return 0;
         
    if (dp[u] != -1) :
        return dp[u];
 
    temp = 0;
    for i in range(n) :
        mask = get_binary(array[i]);
 
        # Recurrence Relation
        if ((mask | u) == u) :
            dp[u] = max(max(0, dp[u ^ mask]) + array[i], dp[u]);
 
    return dp[u];
 
 
# Function to find Maximum Subset Sum
def solve(array, n)  :
    i = 0
     
    # Initialize DP array
    while(i < (1 << 10)) :
        dp[i] = -1;
        i += 1
     
    ans = 0;
 
    i = 0
    # Iterate over all possible masks of 10 bit number
    while(i < (1 << 10)) :
        ans = max(ans, recur(i, array, n));
         
        i += 1
     
    return ans;
 
# Driver Code
if __name__ ==  "__main__" :
 
    array = [ 22, 132, 4, 45, 12, 223 ] ;
    n = len(array);
     
    print(solve(array, n));
     
    # This code is contributed by AnkitRai01

C#

// C# implementation of above approach
using System;
 
class GFG
{
     
static int []dp = new int [1024];
 
// Function to create mask for every number
static int get_binary(int u)
{
    int ans = 0;
    while (u > 0)
     
    {
        int rem = u % 10;
        ans |= (1 << rem);
        u /= 10;
    }
 
    return ans;
}
 
// Recursion for Filling DP array
static int recur(int u, int []array, int n)
{
    // Base Condition
    if (u == 0)
        return 0;
    if (dp[u] != -1)
        return dp[u];
 
    for (int i = 0; i < n; i++)
    {
        int mask = get_binary(array[i]);
 
        // Recurrence Relation
        if ((mask | u) == u)
        {
            dp[u] = Math.Max(Math.Max(0,
                    dp[u ^ mask]) + array[i], dp[u]);
        }
    }
 
    return dp[u];
}
 
// Function to find Maximum Subset Sum
static int solve(int []array, int n)
{
    // Initialize DP array
    for (int i = 0; i < (1 << 10); i++)
    {
        dp[i] = -1;
    }
 
    int ans = 0;
 
    // Iterate over all possible masks of 10 bit number
    for (int i = 0; i < (1 << 10); i++)
    {
        ans = Math.Max(ans, recur(i, array, n));
    }
 
    return ans;
}
 
// Driver Code
static public void Main ()
{
    int []array = { 22, 132, 4, 45, 12, 223 };
    int n = array.Length;
     
    Console.WriteLine (solve(array, n));
}
}
 
// This code is contributed by ajit.

Javascript

<script>
    // Javascript implementation of above approach
     
    let dp = new Array(1024);
    dp.fill(-1);
   
    // Function to create mask for every number
    function get_binary(u)
    {
        let ans = 0;
        while (u > 0)
 
        {
            let rem = u % 10;
            ans |= (1 << rem);
            u = parseInt(u / 10, 10);
        }
 
        return ans;
    }
 
    // Recursion for Filling DP array
    function recur(u, array, n)
    {
        // Base Condition
        if (u == 0)
            return 0;
        if (dp[u] != -1)
            return dp[u];
 
        for (let i = 0; i < n; i++)
        {
            let mask = get_binary(array[i]);
 
            // Recurrence Relation
            if ((mask | u) == u)
            {
                dp[u] = Math.max(Math.max(0,
                        dp[u ^ mask]) + array[i], dp[u]);
            }
        }
 
        return dp[u];
    }
 
    // Function to find Maximum Subset Sum
    function solve(array, n)
    {
        // Initialize DP array
        for (let i = 0; i < (1 << 10); i++)
        {
            dp[i] = -1;
        }
 
        let ans = 0;
 
        // Iterate over all possible masks of 10 bit number
        for (let i = 0; i < (1 << 10); i++)
        {
            ans = Math.max(ans, recur(i, array, n));
        }
 
        return ans;
    }
     
    let array = [ 22, 132, 4, 45, 12, 223 ];
    let n = array.length;
       
    document.write(solve(array, n));
 
</script>
Producción: 

268

 

Complejidad del tiempo: O(N*(2^10))

Espacio auxiliar: O(1024)
 

Publicación traducida automáticamente

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