Encuentre la suma máxima del subconjunto formada al dividir cualquier subconjunto de la array en 2 particiones con la misma suma

Dada una array A que contiene N elementos. Divida cualquier subconjunto de esta array en dos subconjuntos separados de modo que ambos subconjuntos tengan una suma idéntica. Obtenga la suma máxima que se puede obtener después de la partición.

Nota: No es necesario particionar la array completa, es decir, es posible que cualquier elemento no contribuya a ninguna de las particiones.

Ejemplos:

Entrada: A = [1, 2, 3, 6]
Salida: 6
Explicación: Tenemos dos subconjuntos disjuntos {1, 2, 3} y {6}, que tienen la misma suma = 6

Entrada: A = [1, 2, 3, 4, 5, 6]
Salida: 10
Explicación: Tenemos dos subconjuntos disjuntos {2, 3, 5} y {4, 6}, que tienen la misma suma = 10.

Entrada: A = [1, 2]
Salida: 0
Explicación: Ningún subconjunto se puede dividir en 2 subconjuntos disjuntos con suma idéntica

Enfoque ingenuo:
el problema anterior se puede resolver mediante el método de fuerza bruta utilizando la recursividad . Todos los elementos tienen tres posibilidades. O contribuirá a la partición 1 oa la partición 2 o no se incluirá en ninguna de las particiones. Realizaremos estas tres operaciones en cada uno de los elementos y procederemos al siguiente elemento en cada paso recursivo.

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

C++

// CPP implementation for the
// above mentioned recursive approach
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the maximum subset sum
int maxSum(int p0, int p1, int a[], int pos, int n)
{
    if (pos == n) {
        if (p0 == p1)
            return p0;
        else
            return 0;
    }
    // Ignore the current element
    int ans = maxSum(p0, p1, a, pos + 1, n);
 
    // including element in partition 1
    ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
 
    // including element in partition 2
    ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
    return ans;
}
 
// Driver code
int main()
{
    // size of the array
    int n = 4;
    int a[n] = { 1, 2, 3, 6 };
    cout << maxSum(0, 0, a, 0, n);
    return 0;
}

Java

// Java implementation for the
// above mentioned recursive approach
class GFG {
     
    // Function to find the maximum subset sum
    static int maxSum(int p0, int p1, int a[], int pos, int n)
    {
        if (pos == n) {
            if (p0 == p1)
                return p0;
            else
                return 0;
        }
 
        // Ignore the current element
        int ans = maxSum(p0, p1, a, pos + 1, n);
     
        // including element in partition 1
        ans = Math.max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
     
        // including element in partition 2
        ans = Math.max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
        return ans;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        // size of the array
        int n = 4;
        int a[] = { 1, 2, 3, 6 };
        System.out.println(maxSum(0, 0, a, 0, n));
         
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation for the
# above mentioned recursive approach
 
# Function to find the maximum subset sum
def maxSum(p0, p1, a, pos, n) :
 
    if (pos == n) :
        if (p0 == p1) :
            return p0;
        else :
            return 0;
     
    # Ignore the current element
    ans = maxSum(p0, p1, a, pos + 1, n);
 
    # including element in partition 1
    ans = max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
 
    # including element in partition 2
    ans = max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
     
    return ans;
 
# Driver code
if __name__ == "__main__" :
 
    # size of the array
    n = 4;
    a = [ 1, 2, 3, 6 ];
     
    print(maxSum(0, 0, a, 0, n));
 
# This code is contributed by AnkitRai01

C#

// C# implementation for the
// above mentioned recursive approach
 
using System;
 
public class GFG {
     
    // Function to find the maximum subset sum
    static int maxSum(int p0, int p1, int []a, int pos, int n)
    {
        if (pos == n) {
            if (p0 == p1)
                return p0;
            else
                return 0;
        }
 
        // Ignore the current element
        int ans = maxSum(p0, p1, a, pos + 1, n);
     
        // including element in partition 1
        ans = Math.Max(ans, maxSum(p0 + a[pos], p1, a, pos + 1, n));
     
        // including element in partition 2
        ans = Math.Max(ans, maxSum(p0, p1 + a[pos], a, pos + 1, n));
        return ans;
    }
     
    // Driver code
    public static void Main (string[] args)
    {
        // size of the array
        int n = 4;
        int []a = { 1, 2, 3, 6 };
        Console.WriteLine(maxSum(0, 0, a, 0, n));
         
    }
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript implementation for the
// above mentioned recursive approach
 
// Function to find the maximum subset sum
function maxSum(p0, p1, a, pos, n)
{
    if (pos == n)
    {
        if (p0 == p1)
            return p0;
        else
            return 0;
    }
     
    // Ignore the current element
    var ans = maxSum(p0, p1, a, pos + 1, n);
 
    // Including element in partition 1
    ans = Math.max(ans, maxSum(
        p0 + a[pos], p1, a, pos + 1, n));
 
    // Including element in partition 2
    ans = Math.max(ans, maxSum(
        p0, p1 + a[pos], a, pos + 1, n));
    return ans;
}
 
// Driver code
 
// Size of the array
var n = 4;
var a = [ 1, 2, 3, 6 ];
 
document.write(maxSum(0, 0, a, 0, n));
 
// This code is contributed by importantly
 
</script>

Producción:

Complejidad de Tiempo: $O(3^n)$
Espacio Auxiliar: O(n)

Memoización: Aa, podemos ver que hay múltiples subproblemas superpuestos, por lo que en lugar de resolverlos una y otra vez, podemos almacenar cada resultado de llamada recursiva en una array y usarlo.

C++

// CPP implementation for the
// above mentioned recursive approach
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the maximum subset sum
int maxSum(int p0, int p1, int a[], int pos, int n,
           vector<vector<int> >& dp)
{
    if (pos == n) {
        if (p0 == p1)
            return p0;
        else
            return 0;
    }
   //if the value is already computed then return that previous computed value.
    if (dp[pos][p0] != -1) {
        return dp[pos][p0];
    }
   // Ignore the current element
    int ans = maxSum(p0, p1, a, pos + 1, n, dp);
 
    // including element in partition 1
    ans = max(ans,
              maxSum(p0 + a[pos], p1, a, pos + 1, n, dp));
 
    // including element in partition 2
    ans = max(ans,
              maxSum(p0, p1 + a[pos], a, pos + 1, n, dp));
    return dp[pos][p0] = ans;
}
 
int maxSum(int p0, int p1, int a[], int pos, int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
    }
    vector<vector<int> > dp(n, vector<int>(sum + 1, -1));
    return maxSum(p0, p1, a, pos, n, dp);
}
// Driver code
int main()
{
    // size of the array
    int n = 4;
    int a[n] = { 1, 2, 3, 6 };
    cout << maxSum(0, 0, a, 0, n);
 
    return 0;
}

Java

// Java implementation for the
// above mentioned recursive approach
import java.util.Arrays;
class GFG {
 
    // Function to find the maximum subset sum
    static int maxSum(int p0, int p1, int a[], int pos,
                      int n, int[][] dp)
    {
        if (pos == n) {
            if (p0 == p1)
                return p0;
            else
                return 0;
        }
        //if the value is already computed then return that previous computed value.
        if (dp[pos][p0] != -1) {
            return dp[pos][p0];
        }
 
        // Ignore the current element
 
        int ans = maxSum(p0, p1, a, pos + 1, n, dp);
 
        // including element in partition 1
        ans = Math.max(
            ans, maxSum(p0 + a[pos], p1, a, pos + 1, n,dp));
 
        // including element in partition 2
        ans = Math.max(
            ans, maxSum(p0, p1 + a[pos], a, pos + 1, n,dp));
        return dp[pos][p0] = ans;
    }
    static int maxSum(int p0, int p1, int a[], int pos,
                      int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
        }
        int dp[][] = new int[n][sum + 1];
        for (int row[] : dp) {
            Arrays.fill(row, -1);
        }
        return maxSum(p0, p1, a, pos, n, dp);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        // size of the array
        int n = 4;
        int a[] = { 1, 2, 3, 6 };
        System.out.println(maxSum(0, 0, a, 0, n));
    }
}

Producción

Complejidad de tiempo: O(N*Sum), donde Sum representa la suma de todos los elementos de la array.
Espacio auxiliar: O(N*Sum) + O(N) .

Enfoque eficiente:
el método anterior se puede optimizar utilizando el método de programación dinámica .
Definiremos nuestro estado DP de la siguiente manera:

dp[i][j] = Max suma del grupo g0 considerando los primeros i elementos tal que,
la diferencia entre la suma de g0 y g1 es (suma de todos los elementos – j), donde j es la diferencia.
Entonces, la respuesta sería dp[n][suma]

Ahora podemos encontrarnos con que la diferencia entre las sumas es negativa y se encuentra en el rango [-sum, +sum], donde la suma es una suma de todos los elementos. Los rangos mínimo y máximo que ocurren cuando uno de los subconjuntos está vacío y el otro tiene todos los elementos. Por ello, en el estado DP, hemos definido j como (sum – diff). Por lo tanto, j oscilará entre [0, 2*suma].

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

C++

// CPP implementation for the above mentioned
// Dynamic Programming  approach
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the maximum subset sum
int maxSum(int a[], int n)
{
    // sum of all elements
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += a[i];
 
    int limit = 2 * sum + 1;
 
    // bottom up lookup table;
    int dp[n + 1][limit];
 
    // initialising dp table with INT_MIN
    // where, INT_MIN means no solution
    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < limit; j++)
            dp[i][j] = INT_MIN;
    }
 
    // Case when diff is 0
    dp[0][sum] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < limit; j++) {
 
            // Putting ith element in g0
            if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != INT_MIN)
 
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i - 1]]
                                             + a[i - 1]);
 
            // Putting ith element in g1
            if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != INT_MIN)
 
                dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i - 1]]);
 
            // Ignoring ith element
            if (dp[i - 1][j] != INT_MIN)
 
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        }
    }
 
    return dp[n][sum];
}
 
// Driver code
 
int main()
{
    int n = 4;
    int a[n] = { 1, 2, 3, 6 };
    cout << maxSum(a, n);
    return 0;
}

Java

// Java implementation for the above mentioned
// Dynamic Programming approach
class GFG {
     
    final static int INT_MIN = Integer.MIN_VALUE;
     
    // Function to find the maximum subset sum
    static int maxSum(int a[], int n)
    {
        // sum of all elements
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += a[i];
     
        int limit = 2 * sum + 1;
     
        // bottom up lookup table;
        int dp[][] = new int[n + 1][limit];
     
        // initialising dp table with INT_MIN
        // where, INT_MIN means no solution
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < limit; j++)
                dp[i][j] = INT_MIN;
        }
     
        // Case when diff is 0
        dp[0][sum] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < limit; j++) {
     
                // Putting ith element in g0
                if ((j - a[i - 1]) >= 0 && dp[i - 1][j - a[i - 1]] != INT_MIN)
     
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - a[i - 1]]
                                                + a[i - 1]);
     
                // Putting ith element in g1
                if ((j + a[i - 1]) < limit && dp[i - 1][j + a[i - 1]] != INT_MIN)
     
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j + a[i - 1]]);
     
                // Ignoring ith element
                if (dp[i - 1][j] != INT_MIN)
     
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
            }
        }
     
        return dp[n][sum];
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 4;
        int []a = { 1, 2, 3, 6 };
        System.out.println(maxSum(a, n));
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation for the above mentioned
# Dynamic Programming approach
import numpy as np
import sys
 
INT_MIN = -(sys.maxsize - 1)
 
# Function to find the maximum subset sum
def maxSum(a, n) :
 
    # sum of all elements
    sum = 0;
    for i in range(n) :
        sum += a[i];
 
    limit = 2 * sum + 1;
 
    # bottom up lookup table;
    dp = np.zeros((n + 1,limit));
 
    # initialising dp table with INT_MIN
    # where, INT_MIN means no solution
    for i in range(n + 1) :
        for j in range(limit) :
            dp[i][j] = INT_MIN;
 
    # Case when diff is 0
    dp[0][sum] = 0;
    for i in range(1, n + 1) :
        for j in range(limit) :
 
            # Putting ith element in g0
            if ((j - a[i - 1]) >= 0 and dp[i - 1][j - a[i - 1]] != INT_MIN) :
 
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i - 1]]
                                            + a[i - 1]);
 
            # Putting ith element in g1
            if ((j + a[i - 1]) < limit and dp[i - 1][j + a[i - 1]] != INT_MIN) :
 
                dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i - 1]]);
 
            # Ignoring ith element
            if (dp[i - 1][j] != INT_MIN) :
 
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                 
    return dp[n][sum];
 
# Driver code
 
if __name__ == "__main__" :
 
    n = 4;
    a = [ 1, 2, 3, 6 ];
    print(maxSum(a, n));
 
# This code is contributed by Yash_R

C#

// C# implementation for the above mentioned
// Dynamic Programming approach
using System;
 
class GFG {
     
    static int INT_MIN = int.MinValue;
     
    // Function to find the maximum subset sum
    static int maxSum(int []a, int n)
    {
        // sum of all elements
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += a[i];
     
        int limit = 2 * sum + 1;
     
        // bottom up lookup table;
        int [,]dp = new int[n + 1,limit];
     
        // initialising dp table with INT_MIN
        // where, INT_MIN means no solution
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < limit; j++)
                dp[i,j] = INT_MIN;
        }
     
        // Case when diff is 0
        dp[0,sum] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < limit; j++) {
     
                // Putting ith element in g0
                if ((j - a[i - 1]) >= 0 && dp[i - 1,j - a[i - 1]] != INT_MIN)
     
                    dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j - a[i - 1]]
                                                + a[i - 1]);
     
                // Putting ith element in g1
                if ((j + a[i - 1]) < limit && dp[i - 1,j + a[i - 1]] != INT_MIN)
     
                    dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j + a[i - 1]]);
     
                // Ignoring ith element
                if (dp[i - 1,j] != INT_MIN)
     
                    dp[i,j] = Math.Max(dp[i,j], dp[i - 1,j]);
            }
        }
     
        return dp[n,sum];
    }
     
    // Driver code
    public static void Main()
    {
        int n = 4;
        int []a = { 1, 2, 3, 6 };
        Console.WriteLine(maxSum(a, n));
    }
}
 
// This code is contributed by Yash_R

Javascript

<script>
 
 
// JavaScript implementation for the above mentioned
// Dynamic Programming  approach
 
// Function to find the maximum subset sum
function maxSum(a, n)
{
    // sum of all elements
    var sum = 0;
    for (var i = 0; i < n; i++)
        sum += a[i];
 
    var limit = 2 * sum + 1;
 
    // bottom up lookup table;
    var dp = Array.from(Array(n+1), ()=>Array(limit));
 
    // initialising dp table with -1000000000
    // where, -1000000000 means no solution
    for (var i = 0; i < n + 1; i++) {
        for (var j = 0; j < limit; j++)
            dp[i][j] = -1000000000;
    }
 
    // Case when diff is 0
    dp[0][sum] = 0;
    for (var i = 1; i <= n; i++) {
        for (var j = 0; j < limit; j++) {
 
            // Putting ith element in g0
            if ((j - a[i - 1]) >= 0 &&
            dp[i - 1][j - a[i - 1]] != -1000000000)
 
                dp[i][j] = Math.max(dp[i][j],
                dp[i - 1][j - a[i - 1]] + a[i - 1]);
 
            // Putting ith element in g1
            if ((j + a[i - 1]) < limit &&
            dp[i - 1][j + a[i - 1]] != -1000000000)
 
                dp[i][j] = Math.max(dp[i][j],
                dp[i - 1][j + a[i - 1]]);
 
            // Ignoring ith element
            if (dp[i - 1][j] != -1000000000)
 
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
        }
    }
 
    return dp[n][sum];
}
 
// Driver code
var n = 4;
var a = [1, 2, 3, 6];
document.write( maxSum(a, n));
 
</script>

Producción:

Complejidad de tiempo: $O(N*Suma)$ , donde Sum representa la suma de todos los elementos de la array.
Espacio Auxiliar: $O(N*Suma)$

Publicación traducida automáticamente

Artículo escrito por king_tsar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

C++

Java

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta