Dada una array , arr[] de tamaño N , la tarea es encontrar la mediana de las sumas de todos los subconjuntos posibles de la array dada .
Ejemplos:
Entrada: arr = {2, 3, 3}
Salida: 5
Explicación:
Los subconjuntos no vacíos de la array dada son: { {2}, {3}, {3}, {2, 3}, {2, 3} , {3, 3}, {2, 3, 3} }.
Las sumas posibles de cada subconjunto son:
{ {2}, {3}, {3}, {5}, {5}, {6}, {8} }
Por lo tanto, la mediana de todas las sumas posibles de cada subconjunto es 5.Entrada: arr = {1, 2, 1}
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subconjuntos posibles de la array dada y encontrar la suma de los elementos de cada subconjunto. Finalmente, imprima la mediana de todas las posibles sumas de subconjuntos.
Complejidad de Tiempo: O(N * 2 N )
Espacio Auxiliar: O(N * 2 N )
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la programación dinámica . A continuación se muestra la relación de los estados de programación dinámica y los casos base:
Relación entre estados DP:
si j ≥ arr[i] entonces dp[i][j] = dp[i – 1][j] + dp[i – 1][j – arr[i]] De lo contrario, dp
[ i ][j] = dp[i – 1][j]
donde dp[i][j] denota el número total de formas de obtener la suma j ya sea seleccionando el i- ésimo elemento o no seleccionando el i- ésimo elemento.Caso base: dp[i][0] = 1
Siga los pasos a continuación para resolver el problema:
- Inicialice una array 2D , diga DP[][] para almacenar los estados DP mencionados anteriormente.
- Rellene todo el estado dp[][] de abajo hacia arriba utilizando la relación mencionada anteriormente entre los estados DP.
- Inicialice una array, diga sumSub[] para almacenar todas las sumas posibles de cada subconjunto.
- Recorra la array dp[][] y almacene las sumas de todos los subconjuntos posibles en la array sumSub[] .
- Ordene la array sumSub[] .
- Finalmente, imprima el elemento central de la array sumSub[] .
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the median of all
// possible subsets by given operations
int findMedianOfsubSum(int arr[], int N)
{
// Stores sum of elements
// of arr[]
int sum=0;
// Traverse the array arr[]
for(int i=0; i < N; i++) {
// Update sum
sum += arr[i];
}
// Sort the array
sort(arr, arr + N);
// DP[i][j]: Stores total number of ways
// to form the sum j by either selecting
// ith element or not selecting ith item.
int dp[N][sum+1];
// Initialize all
// the DP states
memset(dp, 0, sizeof(dp));
// Base case
for(int i=0; i < N; i++) {
// Fill dp[i][0]
dp[i][0] = 1;
}
// Base case
dp[0][arr[0]] = 1;
// Fill all the DP states based
// on the mentioned DP relation
for(int i = 1; i < N; i++) {
for(int j = 1; j <= sum; j++) {
// If j is greater than
// or equal to arr[i]
if(j >= arr[i]) {
// Update dp[i][j]
dp[i][j] = dp[i-1][j] +
dp[i-1][j-arr[i]];
}
else {
// Update dp[i][j]
dp[i][j] = dp[i-1][j];
}
}
}
// Stores all possible
// subset sum
vector<int> sumSub;
// Traverse all possible subset sum
for(int j=1; j <= sum; j++) {
// Stores count of subsets
// whose sum is j
int M = dp[N - 1][j];
// Iterate over the range [1, M]
for(int i = 1; i <= M; i++) {
// Insert j into sumSub
sumSub.push_back(j);
}
}
// Stores middle element of sumSub
int mid = sumSub[sumSub.size() / 2];
return mid;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMedianOfsubSum(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to calculate the median of all
// possible subsets by given operations
static int findMedianOfsubSum(int arr[], int N)
{
// Stores sum of elements
// of arr[]
int sum = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update sum
sum += arr[i];
}
// Sort the array
Arrays.sort(arr);
// DP[i][j]: Stores total number of ways
// to form the sum j by either selecting
// ith element or not selecting ith item.
int [][]dp = new int[N][sum + 1];
// Initialize all
// the DP states
for(int i = 0; i < N; i++)
{
for(int j = 0; j < sum + 1; j++)
dp[i][j] = 0;
}
// Base case
for(int i = 0; i < N; i++)
{
// Fill dp[i][0]
dp[i][0] = 1;
}
// Base case
dp[0][arr[0]] = 1;
// Fill all the DP states based
// on the mentioned DP relation
for(int i = 1; i < N; i++)
{
for(int j = 1; j <= sum; j++)
{
// If j is greater than
// or equal to arr[i]
if (j >= arr[i])
{
// Update dp[i][j]
dp[i][j] = dp[i - 1][j] +
dp[i - 1][j - arr[i]];
}
else
{
// Update dp[i][j]
dp[i][j] = dp[i - 1][j];
}
}
}
// Stores all possible
// subset sum
Vector<Integer> sumSub = new Vector<Integer>();
// Traverse all possible subset sum
for(int j = 1; j <= sum; j++)
{
// Stores count of subsets
// whose sum is j
int M = dp[N - 1][j];
// Iterate over the range [1, M]
for(int i = 1; i <= M; i++)
{
// Insert j into sumSub
sumSub.add(j);
}
}
// Stores middle element of sumSub
int mid = sumSub.get(sumSub.size() / 2);
return mid;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 2, 3, 3 };
int N = arr.length;
System.out.print(findMedianOfsubSum(arr, N));
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program to implement # the above approach # Function to calculate the # median of all possible subsets # by given operations def findMedianOfsubSum(arr, N): # Stores sum of elements # of arr[] sum = 0 # Traverse the array arr[] for i in range(N): # Update sum sum += arr[i] # Sort the array arr.sort(reverse = False) # DP[i][j]: Stores total number # of ways to form the sum j by # either selecting ith element # or not selecting ith item. dp = [[0 for i in range(sum + 1)] for j in range(N)] # Base case for i in range(N): # Fill dp[i][0] dp[i][0] = 1 # Base case dp[0][arr[0]] = 1 # Fill all the DP states based # on the mentioned DP relation for i in range(1, N, 1): for j in range(1, sum + 1, 1): # If j is greater than # or equal to arr[i] if(j >= arr[i]): # Update dp[i][j] dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - arr[i]]) else: # Update dp[i][j] dp[i][j] = dp[i - 1][j] # Stores all possible # subset sum sumSub = [] # Traverse all possible # subset sum for j in range(1, sum + 1, 1): # Stores count of subsets # whose sum is j M = dp[N - 1][j] # Iterate over the # range [1, M] for i in range(1, M + 1, 1): # Insert j into sumSub sumSub.append(j) # Stores middle element # of sumSub mid = sumSub[len(sumSub) // 2] return mid # Driver Code if __name__ == '__main__': arr = [2, 3, 3] N = len(arr) print(findMedianOfsubSum(arr, N)) # This code is contributed by bgangwar59
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to calculate the median of all
// possible subsets by given operations
static int findMedianOfsubSum(int[] arr, int N)
{
// Stores sum of elements
// of arr[]
int sum = 0;
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update sum
sum += arr[i];
}
// Sort the array
Array.Sort(arr);
// DP[i][j]: Stores total number of ways
// to form the sum j by either selecting
// ith element or not selecting ith item.
int [,]dp = new int[N, sum + 1];
// Initialize all
// the DP states
for(int i = 0; i < N; i++)
{
for(int j = 0; j < sum + 1; j++)
dp[i, j] = 0;
}
// Base case
for(int i = 0; i < N; i++)
{
// Fill dp[i][0]
dp[i, 0] = 1;
}
// Base case
dp[0, arr[0]] = 1;
// Fill all the DP states based
// on the mentioned DP relation
for(int i = 1; i < N; i++)
{
for(int j = 1; j <= sum; j++)
{
// If j is greater than
// or equal to arr[i]
if (j >= arr[i])
{
// Update dp[i][j]
dp[i, j] = dp[i - 1, j] +
dp[i - 1, j - arr[i]];
}
else
{
// Update dp[i][j]
dp[i, j] = dp[i - 1, j];
}
}
}
// Stores all possible
// subset sum
List<int> sumSub = new List<int>();
// Traverse all possible subset sum
for(int j = 1; j <= sum; j++)
{
// Stores count of subsets
// whose sum is j
int M = dp[N - 1, j];
// Iterate over the range [1, M]
for(int i = 1; i <= M; i++)
{
// Insert j into sumSub
sumSub.Add(j);
}
}
// Stores middle element of sumSub
int mid = sumSub[sumSub.Count / 2];
return mid;
}
// Driver code
public static void Main()
{
int[] arr = { 2, 3, 3 };
int N = arr.Length;
Console.Write(findMedianOfsubSum(arr, N));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to calculate the median of all
// possible subsets by given operations
function findMedianOfsubSum(arr, N)
{
// Stores sum of elements
// of arr[]
var sum = 0;
// Traverse the array arr[]
for(var i = 0; i < N; i++)
{
// Update sum
sum += arr[i];
}
// Sort the array
arr.sort((a, b) => a - b)
// DP[i][j]: Stores total number of ways
// to form the sum j by either selecting
// ith element or not selecting ith item.
var dp = Array.from(
Array(N), () => Array(sum + 1).fill(0));
// Base case
for(var i = 0; i < N; i++)
{
// Fill dp[i][0]
dp[i][0] = 1;
}
// Base case
dp[0][arr[0]] = 1;
// Fill all the DP states based
// on the mentioned DP relation
for(var i = 1; i < N; i++)
{
for(var j = 1; j <= sum; j++)
{
// If j is greater than
// or equal to arr[i]
if(j >= arr[i])
{
// Update dp[i][j]
dp[i][j] = dp[i - 1][j] +
dp[i - 1][j - arr[i]];
}
else
{
// Update dp[i][j]
dp[i][j] = dp[i - 1][j];
}
}
}
// Stores all possible
// subset sum
var sumSub = [];
// Traverse all possible subset sum
for(var j = 1; j <= sum; j++)
{
// Stores count of subsets
// whose sum is j
var M = dp[N - 1][j];
// Iterate over the range [1, M]
for(var i = 1; i <= M; i++)
{
// Insert j into sumSub
sumSub.push(j);
}
}
// Stores middle element of sumSub
var mid = sumSub[parseInt(sumSub.length / 2)];
return mid;
}
// Driver Code
var arr = [ 2, 3, 3 ];
var N = arr.length
document.write(findMedianOfsubSum(arr, N));
// This code is contributed by importantly
</script>
Producción
5
Publicación traducida automáticamente
Artículo escrito por Ripunjoy Medhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA