Dada una array arr[] que contiene N enteros y un entero K , la tarea es minimizar la diferencia de la suma del subconjunto después de eliminar K elementos de la array dada.
Nota: Los subconjuntos no deben estar vacíos.
Ejemplos:
Entrada: arr[] = {7, 9, 5, 8, 1, 3}, K = 2
Salida : -23
Explicación : elimine 5 y 3 de la array y forme subconjuntos [1] y [7, 8, 9] .
La diferencia de subconjunto de estos subconjuntos es 1 – 24 = -23 que es la diferencia mínima posible.Entrada: arr[] = {7, 9, 5, 8}, K = 3
Salida: -1
Explicación: Si se eliminan 3 elementos, no es posible formar dos subconjuntos no vacíos.
Enfoque: El problema se puede resolver usando la recursividad basada en la siguiente idea:
Para cada elemento de la array hay 3 opciones : se puede eliminar o ser parte de cualquiera de los dos subconjuntos. Forme todos los subconjuntos posibles después de eliminar K elementos y encuentre aquel en el que la diferencia de las sumas de los subconjuntos sea la mínima.
En lugar de considerar las tres opciones para cada elemento de la array, solo se pueden considerar dos opciones: eliminar o formar parte del primer subconjunto (porque si se conoce la suma de los elementos del primer subconjunto, entonces la suma del otro subconjunto = suma de la array – suma del primer subconjunto)
Siga los pasos mencionados para resolver el problema:
- Calcular la suma de todos los elementos de la array .
- Iterar recursivamente para cada elemento de la array:
- Elimine esto si los elementos K aún no se han eliminado y continúe con el siguiente índice.
- Considere esto como parte de un subconjunto.
- Si se recorre todo el arreglo, verifique la diferencia entre las sumas de dos subconjuntos.
- La diferencia mínima es la respuesta requerida.
A continuación se muestra la implementación del enfoque mencionado anteriormente:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
int mini = INT_MAX;
// Function to form all possible subsets
void subset(vector<int> arr, int index, int sum, int total)
{
if (index >= arr.size()) {
if (sum != 0)
mini = min(mini, sum - (total - sum));
return;
}
subset(arr, index + 1, sum + arr[index], total);
subset(arr, index + 1, sum, total);
}
// Function to get the minimum difference
static void print(int index, vector<int>& arr, int total,
vector<int>& ans)
{
if (total == 0) {
int sum = 0;
for (int elements : ans) {
sum += elements;
}
// Function call to form subset
subset(ans, 0, 0, sum);
return;
}
if (index >= arr.size()) {
return;
}
ans.push_back(arr[index]);
print(index + 1, arr, total - 1, ans);
ans.pop_back();
print(index + 1, arr, total, ans);
}
// Utility function to solve the problem
void solve(vector<int>& arr, int N)
{
int selected = arr.size() - N;
if (selected <= 1) {
cout << -1;
return;
}
vector<int> ans;
print(0, arr, selected, ans);
}
// Driver code
int main()
{
vector<int> arr = { 7, 9, 5, 8, 1, 3 };
int N = 2;
solve(arr, N);
cout << (mini);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
static int min = Integer.MAX_VALUE;
// Function to form all possible subsets
static void subset(List<Integer> arr,
int index,
int sum, int total)
{
if (index >= arr.size()) {
if (sum != 0)
min = Math.min(min,
sum - (total - sum));
return;
}
subset(arr, index + 1,
sum + arr.get(index), total);
subset(arr, index + 1, sum, total);
}
// Function to get the minimum difference
static void print(int index, int arr[],
int total,
List<Integer> ans)
{
if (total == 0) {
int sum = 0;
for (int elements : ans) {
sum += elements;
}
// Function call to form subset
subset(ans, 0, 0, sum);
return;
}
if (index >= arr.length) {
return;
}
ans.add(arr[index]);
print(index + 1, arr, total - 1, ans);
ans.remove(ans.size() - 1);
print(index + 1, arr, total, ans);
}
// Utility function to solve the problem
public static void solve(int arr[], int N)
{
int selected = arr.length - N;
if (selected <= 1) {
System.out.println(-1);
return;
}
List<Integer> ans = new ArrayList<>();
print(0, arr, selected, ans);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 7, 9, 5, 8, 1, 3 };
int N = 2;
solve(arr, N);
System.out.println(min);
}
}
Python3
# Python code to implement the above approach import sys # Function to form all possible subsets def subset(arr,index,sum,total): global mini if (index >= len(arr)): if (sum != 0): mini = min(mini, sum - (total - sum)) return subset(arr, index + 1, sum + arr[index], total) subset(arr, index + 1, sum, total) # Function to get the minimum difference def Print(index,arr,total,ans): if (total == 0): sum = 0 for elements in ans: sum += elements # Function call to form subset subset(ans, 0, 0, sum) return if (index >= len(arr)): return ans.append(arr[index]) Print(index + 1, arr, total - 1, ans) ans.pop() Print(index + 1, arr, total, ans) # Utility function to solve the problem def solve(arr,N): selected = len(arr) - N if (selected <= 1): print(-1) return ans = [] Print(0, arr, selected, ans) # Driver code if __name__=="__main__": mini = sys.maxsize arr = [ 7, 9, 5, 8, 1, 3 ] N = 2 solve(arr, N) print(mini) # This code is contributed by shinjanpatra
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int min = Int32.MaxValue;
// Function to form all possible subsets
static void subset(List<int> arr,
int index,
int sum, int total)
{
if (index >= arr.Count) {
if (sum != 0)
min = Math.Min(min,
sum - (total - sum));
return;
}
subset(arr, index + 1,
sum + arr[index], total);
subset(arr, index + 1, sum, total);
}
// Function to get the minimum difference
static void print(int index, int[] arr,
int total,
List<int> ans)
{
if (total == 0) {
int sum = 0;
foreach (int elements in ans) {
sum += elements;
}
// Function call to form subset
subset(ans, 0, 0, sum);
return;
}
if (index >= arr.Length) {
return;
}
ans.Add(arr[index]);
print(index + 1, arr, total - 1, ans);
ans.RemoveAt(ans.Count - 1);
print(index + 1, arr, total, ans);
}
// Utility function to solve the problem
public static void solve(int[] arr, int N)
{
int selected = arr.Length - N;
if (selected <= 1) {
Console.Write(-1);
return;
}
List<int> ans = new List<int>();
print(0, arr, selected, ans);
}
// Driver Code
public static void Main()
{
int[] arr = { 7, 9, 5, 8, 1, 3 };
int N = 2;
solve(arr, N);
Console.Write(min);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code to implement the above approach
let mini = Number.MAX_VALUE;
// Function to form all possible subsets
function subset(arr,index,sum,total)
{
if (index >= arr.length) {
if (sum != 0)
mini = Math.min(mini, sum - (total - sum));
return;
}
subset(arr, index + 1, sum + arr[index], total);
subset(arr, index + 1, sum, total);
}
// Function to get the minimum difference
function print(index,arr,total,ans)
{
if (total == 0) {
sum = 0;
for (let elements of ans) {
sum += elements;
}
// Function call to form subset
subset(ans, 0, 0, sum);
return;
}
if (index >= arr.length) {
return;
}
ans.push(arr[index]);
print(index + 1, arr, total - 1, ans);
ans.pop();
print(index + 1, arr, total, ans);
}
// Utility function to solve the problem
function solve(arr,N)
{
let selected = arr.length - N;
if (selected <= 1) {
document.write(-1);
return;
}
let ans = [];
print(0, arr, selected, ans);
}
// Driver code
let arr = [ 7, 9, 5, 8, 1, 3 ];
let N = 2;
solve(arr, N);
document.write(mini);
// This code is contributed by shinjanpatra
</script>
-23
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por zack_aayush y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA