Dada una array de tamaño N . La tarea es dividir la array dada en dos subconjuntos de modo que el promedio de todos los elementos en ambos subconjuntos sea igual. Si no existe tal partición, imprima -1. De lo contrario, imprima las particiones. Si existen múltiples soluciones, imprima la solución donde la longitud del primer subconjunto sea mínima. Si todavía hay un empate, imprima las particiones donde el primer subconjunto es lexicográficamente más pequeño.
Ejemplos:
Input : vec[] = {1, 7, 15, 29, 11, 9}
Output : [9, 15] [1, 7, 11, 29]
Explanation : Average of the both the subsets is 12
Input : vec[] = {1, 2, 3, 4, 5, 6}
Output : [1, 6] [2, 3, 4, 5].
Explanation : Another possible solution is [3, 4] [1, 2, 5, 6],
but print the solution whose first subset is lexicographically
smallest.
Observación:
si calculamos directamente el promedio de un determinado subconjunto y lo comparamos con el promedio de otro subconjunto, debido a problemas de precisión con los compiladores, se producirán resultados inesperados. Por ejemplo, 5/3 = 1,66666… y 166/100 = 1,66. Algunos compiladores pueden tratarlos como iguales, mientras que otros no lo harán.
Sea sub1 y sub2 la suma de dos subconjuntos en consideración, y sean sus tamaños s1 y s2. Si sus promedios son iguales, sub1/s1 = sub2/s2. Lo que significa sub1*s2 = sub2*s1.
También la suma total de los dos subconjuntos anteriores = sub1+sub2, y s2= tamaño total – s1.
Simplificando lo anterior, obtenemos
(sub1/s1) = (sub1+sub2)/ (s1+s2) = (suma total) / (tamaño total).
Ahora este problema se reduce al hecho de que si podemos seleccionar un tamaño particular
de subconjunto cuya suma es igual a la suma del subconjunto actual, hemos terminado.
Enfoque:
definamos la función de partición (ind, curr_sum, curr_size), que devuelve verdadero si es posible construir un subconjunto usando elementos con índice igual a ind y tamaño igual a curr_size y suma igual a curr_sum.
Esta relación recursiva se puede definir como:
partición(ind, curr_sum, curr_size) = partición(ind+1, curr_sum, curr_size) || partición(ind+1, curr_sum – val[ind], curr_size-1).
Dos partes en el lado derecho de las ecuaciones anteriores representan si incluimos el elemento en el índice ind o no.
Esta es una desviación del clásico problema de suma de subconjuntos , en el que los subproblemas se evalúan una y otra vez. Por lo tanto memorizamos los subproblemas y los convertimos en una solución de Programación Dinámica .
C++14
// C++ program to Partition an array of
// non-negative integers into two subsets
// such that average of both the subsets are equal
#include <bits/stdc++.h>
using namespace std;
vector<vector<vector<bool> > > dp;
vector<int> res;
vector<int> original;
int total_size;
// Function that returns true if it is possible to
// use elements with index = ind to construct a set of s
// ize = curr_size whose sum is curr_sum.
bool possible(int index, int curr_sum, int curr_size)
{
// base cases
if (curr_size == 0)
return (curr_sum == 0);
if (index >= total_size)
return false;
// Which means curr_sum cant be found for curr_size
if (dp[index][curr_sum][curr_size] == false)
return false;
if (curr_sum >= original[index]) {
res.push_back(original[index]);
// Checks if taking this element at
// index i leads to a solution
if (possible(index + 1, curr_sum -
original[index],
curr_size - 1))
return true;
res.pop_back();
}
// Checks if not taking this element at
// index i leads to a solution
if (possible(index + 1, curr_sum, curr_size))
return true;
// If no solution has been found
return dp[index][curr_sum][curr_size] = false;
}
// Function to find two Partitions having equal average
vector<vector<int> > partition(vector<int>& Vec)
{
// Sort the vector
sort(Vec.begin(), Vec.end());
original.clear();
original = Vec;
dp.clear();
res.clear();
int total_sum = 0;
total_size = Vec.size();
for (int i = 0; i < total_size; ++i)
total_sum += Vec[i];
// building the memoization table
dp.resize(original.size(), vector<vector<bool> >
(total_sum + 1, vector<bool>(total_size, true)));
for (int i = 1; i < total_size; i++) {
// Sum_of_Set1 has to be an integer
if ((total_sum * i) % total_size != 0)
continue;
int Sum_of_Set1 = (total_sum * i) / total_size;
// We build our solution vector if its possible
// to find subsets that match our criteria
// using a recursive function
if (possible(0, Sum_of_Set1, i)) {
// Find out the elements in Vec, not in
// res and return the result.
int ptr1 = 0, ptr2 = 0;
vector<int> res1 = res;
vector<int> res2;
while (ptr1 < Vec.size() || ptr2 < res.size())
{
if (ptr2 < res.size() &&
res[ptr2] == Vec[ptr1])
{
ptr1++;
ptr2++;
continue;
}
res2.push_back(Vec[ptr1]);
ptr1++;
}
vector<vector<int> > ans;
ans.push_back(res1);
ans.push_back(res2);
return ans;
}
}
// If we havent found any such subset.
vector<vector<int> > ans;
return ans;
}
// Function to print partitions
void Print_Partition(vector<vector<int> > sol)
{
// Print two partitions
for (int i = 0; i < sol.size(); i++) {
cout << "[";
for (int j = 0; j < sol[i].size(); j++) {
cout << sol[i][j];
if (j != sol[i].size() - 1)
cout << " ";
}
cout << "] ";
}
}
// Driver code
int main()
{
vector<int> Vec = { 1, 7, 15, 29, 11, 9 };
vector<vector<int> > sol = partition(Vec);
// If partition possible
if (sol.size())
Print_Partition(sol);
else
cout << -1;
return 0;
}
Java
// Java program to Partition an array of
// non-negative integers into two subsets
// such that average of both the subsets are equal
import java.io.*;
import java.util.*;
class GFG
{
static boolean[][][] dp;
static Vector<Integer> res = new Vector<>();
static int[] original;
static int total_size;
// Function that returns true if it is possible to
// use elements with index = ind to construct a set of s
// ize = curr_size whose sum is curr_sum.
static boolean possible(int index, int curr_sum,
int curr_size)
{
// base cases
if (curr_size == 0)
return (curr_sum == 0);
if (index >= total_size)
return false;
// Which means curr_sum cant be found for curr_size
if (dp[index][curr_sum][curr_size] == false)
return false;
if (curr_sum >= original[index])
{
res.add(original[index]);
// Checks if taking this element at
// index i leads to a solution
if (possible(index + 1, curr_sum - original[index],
curr_size - 1))
return true;
res.remove(res.size() - 1);
}
// Checks if not taking this element at
// index i leads to a solution
if (possible(index + 1, curr_sum, curr_size))
return true;
// If no solution has been found
return dp[index][curr_sum][curr_size] = false;
}
// Function to find two Partitions having equal average
static Vector<Vector<Integer>> partition(int[] Vec)
{
// Sort the vector
Arrays.sort(Vec);
original = Vec;
res.clear();
int total_sum = 0;
total_size = Vec.length;
for (int i = 0; i < total_size; ++i)
total_sum += Vec[i];
// building the memoization table
dp = new boolean[original.length][total_sum + 1][total_size];
for (int i = 0; i < original.length; i++)
for (int j = 0; j < total_sum + 1; j++)
for (int k = 0; k < total_size; k++)
dp[i][j][k] = true;
for (int i = 1; i < total_size; i++)
{
// Sum_of_Set1 has to be an integer
if ((total_sum * i) % total_size != 0)
continue;
int Sum_of_Set1 = (total_sum * i) / total_size;
// We build our solution vector if its possible
// to find subsets that match our criteria
// using a recursive function
if (possible(0, Sum_of_Set1, i))
{
// Find out the elements in Vec, not in
// res and return the result.
int ptr1 = 0, ptr2 = 0;
Vector<Integer> res1 = res;
Vector<Integer> res2 = new Vector<>();
while (ptr1 < Vec.length || ptr2 < res.size())
{
if (ptr2 < res.size() &&
res.elementAt(ptr2) == Vec[ptr1])
{
ptr1++;
ptr2++;
continue;
}
res2.add(Vec[ptr1]);
ptr1++;
}
Vector<Vector<Integer>> ans = new Vector<>();
ans.add(res1);
ans.add(res2);
return ans;
}
}
// If we havent found any such subset.
Vector<Vector<Integer>> ans = new Vector<>();
return ans;
}
// Function to print partitions
static void Print_Partition(Vector<Vector<Integer>> sol)
{
// Print two partitions
for (int i = 0; i < sol.size(); i++)
{
System.out.print("[");
for (int j = 0; j < sol.elementAt(i).size(); j++)
{
System.out.print(sol.elementAt(i).elementAt(j));
if (j != sol.elementAt(i).size() - 1)
System.out.print(" ");
}
System.out.print("]");
}
}
// Driver Code
public static void main(String[] args)
{
int[] Vec = { 1, 7, 15, 29, 11, 9 };
Vector<Vector<Integer>> sol = partition(Vec);
// If partition possible
if (sol.size() > 0)
Print_Partition(sol);
else
System.out.println("-1");
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to partition an array of
# non-negative integers into two subsets
# such that average of both the subsets are equal
dp = []
res = []
original = []
total_size = int(0)
# Function that returns true if it is possible
# to use elements with index = ind to construct
# a set of s ize = curr_size whose sum is curr_sum.
def possible(index, curr_sum, curr_size):
index = int(index)
curr_sum = int(curr_sum)
curr_size = int(curr_size)
global dp, res
# Base cases
if curr_size == 0:
return (curr_sum == 0)
if index >= total_size:
return False
# Which means curr_sum cant be
# found for curr_size
if dp[index][curr_sum][curr_size] == False:
return False
if curr_sum >= original[index]:
res.append(original[index])
# Checks if taking this element
# at index i leads to a solution
if possible(index + 1,
curr_sum - original[index],
curr_size - 1):
return True
res.pop()
# Checks if not taking this element at
# index i leads to a solution
if possible(index + 1, curr_sum, curr_size):
return True
# If no solution has been found
dp[index][curr_sum][curr_size] = False
return False
# Function to find two partitions
# having equal average
def partition(Vec):
global dp, original, res, total_size
# Sort the vector
Vec.sort()
if len(original) > 0:
original.clear()
original = Vec
if len(dp) > 0:
dp.clear()
if len(res) > 0:
res.clear()
total_sum = 0
total_size = len(Vec)
for i in range(total_size):
total_sum += Vec[i]
# Building the memoization table
dp = [[[True for _ in range(total_size)]
for _ in range(total_sum + 1)]
for _ in range(len(original))]
for i in range(1, total_size):
# Sum_of_Set1 has to be an integer
if (total_sum * i) % total_size != 0:
continue
Sum_of_Set1 = (total_sum * i) / total_size
# We build our solution vector if its possible
# to find subsets that match our criteria
# using a recursive function
if possible(0, Sum_of_Set1, i):
# Find out the elements in Vec,
# not in res and return the result.
ptr1 = 0
ptr2 = 0
res1 = res
res2 = []
while ptr1 < len(Vec) or ptr2 < len(res):
if (ptr2 < len(res) and
res[ptr2] == Vec[ptr1]):
ptr1 += 1
ptr2 += 1
continue
res2.append(Vec[ptr1])
ptr1 += 1
ans = []
ans.append(res1)
ans.append(res2)
return ans
# If we havent found any such subset.
ans = []
return ans
# Driver code
Vec = [ 1, 7, 15, 29, 11, 9 ]
sol = partition(Vec)
if len(sol) > 0:
print(sol)
else:
print("-1")
# This code is contributed by saishashank1
C#
// C# program to Partition an array of
// non-negative integers into two subsets
// such that average of both the subsets are equal
using System;
using System.Collections;
class GFG{
static bool[,,] dp;
static ArrayList res = new ArrayList();
static int[] original;
static int total_size;
// Function that returns true if it is possible to
// use elements with index = ind to construct a set of s
// ize = curr_size whose sum is curr_sum.
static bool possible(int index, int curr_sum,
int curr_size)
{
// base cases
if (curr_size == 0)
return (curr_sum == 0);
if (index >= total_size)
return false;
// Which means curr_sum cant be
// found for curr_size
if (dp[index, curr_sum, curr_size] == false)
return false;
if (curr_sum >= original[index])
{
res.Add(original[index]);
// Checks if taking this element at
// index i leads to a solution
if (possible(index + 1, curr_sum -
original[index], curr_size - 1))
return true;
res.Remove(res[res.Count - 1]);
}
// Checks if not taking this element at
// index i leads to a solution
if (possible(index + 1, curr_sum, curr_size))
return true;
dp[index, curr_sum, curr_size] = false;
// If no solution has been found
return dp[index, curr_sum, curr_size];
}
// Function to find two Partitions
// having equal average
static ArrayList partition(int[] Vec)
{
// Sort the vector
Array.Sort(Vec);
original = Vec;
res.Clear();
int total_sum = 0;
total_size = Vec.Length;
for(int i = 0; i < total_size; ++i)
total_sum += Vec[i];
// Building the memoization table
dp = new bool[original.Length,
total_sum + 1,
total_size];
for(int i = 0; i < original.Length; i++)
for(int j = 0; j < total_sum + 1; j++)
for(int k = 0; k < total_size; k++)
dp[i, j, k] = true;
for(int i = 1; i < total_size; i++)
{
// Sum_of_Set1 has to be an integer
if ((total_sum * i) % total_size != 0)
continue;
int Sum_of_Set1 = (total_sum * i) / total_size;
// We build our solution vector if its possible
// to find subsets that match our criteria
// using a recursive function
if (possible(0, Sum_of_Set1, i))
{
// Find out the elements in Vec, not in
// res and return the result.
int ptr1 = 0, ptr2 = 0;
ArrayList res1 = new ArrayList(res);
ArrayList res2 = new ArrayList();
while (ptr1 < Vec.Length || ptr2 < res.Count)
{
if (ptr2 < res.Count &&
(int)res[ptr2] == Vec[ptr1])
{
ptr1++;
ptr2++;
continue;
}
res2.Add(Vec[ptr1]);
ptr1++;
}
ArrayList ans = new ArrayList();
ans.Add(res1);
ans.Add(res2);
return ans;
}
}
// If we havent found any such subset.
ArrayList ans2 = new ArrayList();
return ans2;
}
// Function to print partitions
static void Print_Partition(ArrayList sol)
{
// Print two partitions
for(int i = 0; i < sol.Count; i++)
{
Console.Write("[");
for(int j = 0; j < ((ArrayList)sol[i]).Count; j++)
{
Console.Write((int)((ArrayList)sol[i])[j]);
if (j != ((ArrayList)sol[i]).Count - 1)
Console.Write(" ");
}
Console.Write("] ");
}
}
// Driver Code
public static void Main(string[] args)
{
int[] Vec = { 1, 7, 15, 29, 11, 9 };
ArrayList sol = partition(Vec);
// If partition possible
if (sol.Count > 0)
Print_Partition(sol);
else
Console.Write("-1");
}
}
// This code is contributed by rutvik_56
Producción:
[9 15] [1 7 11 29]
Complejidad temporal: O(n 3 )
Espacio Auxiliar: O(n 3 )
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