Suma sobre subconjuntos | Programación dinámica

Requisito previo: programación dinámica básica , máscaras
de bits Considere el siguiente problema en el que usaremos la suma sobre el subconjunto de programación dinámica para resolverlo.
Dada una array de 2 ⁿ enteros, necesitamos calcular la función F(x) = ∑A _i tal que x&i==i para todo xie, i es un subconjunto bit a bit de x. seré un subconjunto bit a bit de la máscara x, si x&i==i.
Ejemplos:

Input: A[] = {7, 12, 14, 16}  ,  n = 2
Output: 7, 19, 21, 49
Explanation: There will be 4 values of x: 0,1,2,3
So, we need to calculate F(0),F(1),F(2),F(3).
Now, F(0) = A₀ = 7 
F(1) =  A₀ + A₁ = 19
F(2) = A₀ + A₂ = 21
F(3) = A₀ + A₁ + A₂ + A₃ = 49

Input: A[] = {7, 11, 13, 16}  ,  n = 2
Output: 7, 18, 20, 47 
Explanation: There will be 4 values of x: 0,1,2,3
So, we need to calculate F(0),F(1),F(2),F(3).
Now, F(0) = A₀ = 7 
F(1) =  A₀ + A₁ = 18
F(2) = A₀ + A₂ = 20
F(3) = A₀ + A₁ + A₂ + A₃ = 47

Enfoque de fuerza bruta:
Iterar para todas las x de 0 a (2 ⁿ -1) . Calcule los subconjuntos bit a bit de todos los x y súmelos para cada x.
Complejidad de tiempo: O (4 ^ n)
A continuación se muestra la implementación de la idea anterior:

C++

// CPP program for brute force
// approach of SumOverSubsets DP
#include <bits/stdc++.h>
using namespace std;
 
// function to print the sum over subsets value
void SumOverSubsets(int a[], int n) {
 
  // array to store the SumOverSubsets
  int sos[1 << n] = {0};
 
  // iterate for all possible x
  for (int x = 0; x < (1 << n); x++) {
 
    // iterate for all possible bitwise subsets
    for (int i = 0; i < (1 << n); i++) {
 
      // if i is a bitwise subset of x
      if ((x & i) == i)
        sos[x] += a[i];
    }
  }
 
  // printa all the subsets
  for (int i = 0; i < (1 << n); i++)
    cout << sos[i] << " ";
}
 
// Driver Code
int main() {
  int a[] = {7, 12, 14, 16};
  int n = 2;
  SumOverSubsets(a, n);
  return 0;
}

Java

// Java program for brute force
// approach of SumOverSubsets DP
 
class GFG{
 
// function to print the
// sum over subsets value
static void SumOverSubsets(int a[], int n) {
 
// array to store the SumOverSubsets
int sos[] = new int [1 << n];
 
 
// iterate for all possible x
for (int x = 0; x < (1 << n); x++) {
 
    // iterate for all possible
        // bitwise subsets
    for (int i = 0; i < (1 << n); i++) {
 
    // if i is a bitwise subset of x
    if ((x & i) == i)
        sos[x] += a[i];
    }
}
 
// printa all the subsets
for (int i = 0; i < (1 << n); i++)
    System.out.printf("%d ", sos[i]);
}
 
// Driver Code
public static void main(String[] args) {
int a[] = {7, 12, 14, 16};
int n = 2;
SumOverSubsets(a, n);
}
}
 
// This code is contributed by
// Smitha Dinesh Semwal

Python3

# Python 3 program
# for brute force
# approach of SumOverSubsets DP
 
# function to print the
# sum over subsets value
def SumOverSubsets(a, n):
 
    # array to store
    # the SumOverSubsets
    sos = [0] * (1 << n)
     
    # iterate for all possible x
    for x in range(0,(1 << n)):
     
        # iterate for all
        # possible bitwise subsets
        for i in range(0,(1 << n)): 
     
            # if i is a bitwise subset of x
            if ((x & i) == i):
                sos[x] += a[i]
             
     
     
    # printa all the subsets
    for i in range(0,(1 << n)):
        print(sos[i],end = " ")
 
 
# Driver Code
a = [7, 12, 14, 16]
n = 2
SumOverSubsets(a, n)
 
# This code is contributed by
# Smitha Dinesh Semwal

C#

// C# program for brute force
// approach of SumOverSubsets DP
using System;
 
class GFG {
     
    // function to print the
    // sum over subsets value
    static void SumOverSubsets(int []a, int n)
    {
     
        // array to store the SumOverSubsets
        int []sos = new int [1 << n];
         
         
        // iterate for all possible x
        for (int x = 0; x < (1 << n); x++)
        {
         
            // iterate for all possible
            // bitwise subsets
            for (int i = 0; i < (1 << n); i++)
            {
         
                // if i is a bitwise subset of x
                if ((x & i) == i)
                    sos[x] += a[i];
            }
        }
         
        // printa all the subsets
        for (int i = 0; i < (1 << n); i++)
            Console.Write(sos[i] + " ");
    }
     
    // Driver function
    public static void Main()
    {
        int []a = {7, 12, 14, 16};
        int n = 2;
        SumOverSubsets(a, n);
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program for brute force
// approach of SumOverSubsets DP
 
// function to print the sum
// over subsets value
function SumOverSubsets($a, $n)
{
 
    // array to store the SumOverSubsets
    $sos = array(1 << $n);
     
    for($i = 0 ;$i < (1 << $n); $i++)
        $sos[$i] = 0;
     
    // iterate for all possible x
    for ($x = 0; $x < (1 << $n); $x++)
    {
     
        // iterate for all possible
        // bitwise subsets
        for($i = 0; $i < (1 << $n); $i++)
        {
     
            // if i is a bitwise
            // subset of x
            if (($x & $i) == $i)
                $sos[$x] += $a[$i];
        }
    }
     
    // printa all the subsets
    for ($i = 0; $i < (1 << $n); $i++)
        echo $sos[$i] . " ";
}
 
// Driver Code
$a = array(7, 12, 14, 16);
$n = 2;
SumOverSubsets($a, $n);
 
// This code is contributed by Sam007
?>

Javascript

<script>
    // Javascript program for brute force
    // approach of SumOverSubsets DP
     
    // function to print the
    // sum over subsets value
    function SumOverSubsets(a, n)
    {
      
        // array to store the SumOverSubsets
        let sos = new Array(1 << n);
        sos.fill(0);
          
          
        // iterate for all possible x
        for (let x = 0; x < (1 << n); x++)
        {
          
            // iterate for all possible
            // bitwise subsets
            for (let i = 0; i < (1 << n); i++)
            {
          
                // if i is a bitwise subset of x
                if ((x & i) == i)
                    sos[x] += a[i];
            }
        }
          
        // printa all the subsets
        for (let i = 0; i < (1 << n); i++)
            document.write(sos[i] + " ");
    }
     
    let a = [7, 12, 14, 16];
    let n = 2;
    SumOverSubsets(a, n);
         
</script>

Producción:

7 19 21 49

.
Enfoque subóptimo:
el algoritmo de fuerza bruta se puede mejorar fácilmente simplemente iterando sobre subconjuntos bit a bit. En lugar de iterar para cada i, podemos simplemente iterar solo para los subconjuntos bit a bit. Iterar hacia atrás para i=(i-1)&x nos da cada subconjunto bit a bit, donde i comienza desde x y termina en 1. Si la máscara x tiene k bits establecidos, hacemos 2 ^k iteraciones. ^{Un número de k} bits establecidos tendrá 2k subconjuntos bit a bit. Por lo tanto, el número total de máscaras x con k bits establecidos es ${n \elegir k}$ . Por lo tanto, el número total de iteraciones es ∑ ${n \elegir k}$ 2 ^k = 3 ⁿ
Complejidad de tiempo: O(3 ⁿ )
A continuación se muestra la implementación de la idea anterior:

C++

// CPP program for sub-optimal
// approach of SumOverSubsets DP
#include <bits/stdc++.h>
using namespace std;
 
// function to print the sum over subsets value
void SumOverSubsets(int a[], int n) {
 
  // array to store the SumOverSubsets
  int sos[1 << n] = {0};
 
  // iterate for all possible x
  for (int x = 0; x < (1 << n); x++) {
    sos[x] = a[0];
 
    // iterate for the bitwise subsets only
    for (int i = x; i > 0; i = (i - 1) & x)
      sos[x] += a[i];
  }
 
  // print all the subsets
  for (int i = 0; i < (1 << n); i++)
    cout << sos[i] << " ";
}
 
// Driver Code
int main() {
  int a[] = {7, 12, 14, 16};
  int n = 2;
  SumOverSubsets(a, n);
  return 0;
}

Java

// java program for sub-optimal
// approach of SumOverSubsets DP
public class GFG {
     
    // function to print the sum over
    // subsets value
    static void SumOverSubsets(int a[], int n)
    {
     
        // array to store the SumOverSubsets
        int sos[] = new int[(1 << n)];
         
        // iterate for all possible x
        for (int x = 0; x < (1 << n); x++) {
            sos[x] = a[0];
         
            // iterate for the bitwise subsets only
            for (int i = x; i > 0; i = (i - 1) & x)
                sos[x] += a[i];
        }
         
        // print all the subsets
        for (int i = 0; i < (1 << n); i++)
            System.out.print(sos[i] + " ");
    }
     
    // Driver code
    public static void main(String args[])
    {
        int a[] = {7, 12, 14, 16};
        int n = 2;
         
        SumOverSubsets(a, n);
    }
}
 
// This code is contributed by Sam007

Python3

# Python program for sub-optimal
# approach of SumOverSubsets DP
 
# function to print sum over subsets value
def SumOverSubsets(a, n):
    sos = [0]*(1 << n)
 
    # iterate for all possible x
    for x in range((1 << n)):
        sos[x] = a[0]
         
        # iterate for the bitwise subsets only
        i = x
 
        while i > 0:
          sos[x] += a[i]
          i = ((i - 1) & x)
 
  # print all the subsets
    for i in range(1<<n):
        print(sos[i], end = " ")
 
# Driver Code
if __name__ == '__main__':
    a = [7, 12, 14, 16]
    n = 2
    SumOverSubsets(a, n)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for sub-optimal
// approach of SumOverSubsets DP
using System;
 
class GFG {
     
    // function to print the sum over
    // subsets value
    static void SumOverSubsets(int []a, int n)
    {
     
        // array to store the SumOverSubsets
        int []sos = new int[(1 << n)];
         
        // iterate for all possible x
        for (int x = 0; x < (1 << n); x++) {
            sos[x] = a[0];
         
            // iterate for the bitwise subsets only
            for (int i = x; i > 0; i = (i - 1) & x)
                sos[x] += a[i];
        }
         
        // print all the subsets
        for (int i = 0; i < (1 << n); i++)
        Console.Write(sos[i] + " ");
    }
     
    // Driver code
    static void Main()
    {
        int []a = {7, 12, 14, 16};
        int n = 2;
         
        SumOverSubsets(a, n);
    }
}
 
// This code is contributed by Sam007.

PHP

<?php
// PHP program for sub-optimal
// approach of SumOverSubsets DP
 
// function to print the
// sum over subsets value
function SumOverSubsets($a,$n)
{
 
    // array to store the SumOverSubsets
    $sos=array(1 << $n);
     
    // iterate for all possible x
    for ($x = 0; $x < (1 << $n); $x++)
    {
        $sos[$x] = $a[0];
     
        // iterate for the bitwise
        // subsets only
        for ($i = $x; $i > 0; $i = ($i - 1) & $x)
        $sos[$x] += $a[$i];
    }
     
    // print all the subsets
    for ($i = 0; $i < (1 << $n); $i++)
        echo $sos[$i] . " ";
}
 
// Driver Code
$a = array(7, 12, 14, 16);
$n = 2;
SumOverSubsets($a, $n);
 
// This code is contributed by Sam007.
?>

Javascript

<script>   
    // Javascript program for sub-optimal
    // approach of SumOverSubsets DP
     
    // function to print the sum over
    // subsets value
    function SumOverSubsets(a, n)
    {
      
        // array to store the SumOverSubsets
        let sos = new Array((1 << n));
        sos.fill(0);
          
        // iterate for all possible x
        for (let x = 0; x < (1 << n); x++) {
            sos[x] = a[0];
          
            // iterate for the bitwise subsets only
            for (let i = x; i > 0; i = (i - 1) & x)
                sos[x] += a[i];
        }
          
        // print all the subsets
        for (let i = 0; i < (1 << n); i++)
            document.write(sos[i] + " ");
    }
     
    let a = [7, 12, 14, 16];
    let n = 2;
 
    SumOverSubsets(a, n);
 
</script>

Producción:

7 19 21 49

Complejidad de tiempo: O(n*2 ⁿ )
Espacio auxiliar : O(n ² )
Referencia :
http://home.iitk.ac.in/~gsahil/cs498a/report.pdf

Publicación traducida automáticamente

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

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

PHP

Javascript

Deja una respuesta Cancelar la respuesta