Tamaño mínimo del subconjunto de pares cuya suma es al menos los elementos restantes de la array

Dados dos arreglos A[] y B[], ambos compuestos por N enteros positivos, la tarea es encontrar el tamaño mínimo de los subconjuntos de un par de elementos (A[i], B[i]) tales que la suma de todos los pares de subconjuntos es al menos la suma de los elementos restantes de la array A[] que no están incluidos en el subconjunto, es decir, (A[0] + B[0] + A[1] + B[1] + … + A[K – 1] + B[K – 1] >= A[K + 1] + … + A[N – 1] .

Ejemplos:

Entrada: A[] = {3, 2, 2}, B[] = {2, 3, 1}
Salida: 1
Explicación:
Elija el subconjunto como {(3, 2)}. Ahora, la suma de los subconjuntos es 3 + 2 = 5, que es mayor que la suma de los restantes A[] = 3 + 1 = 4.

Entrada: A[] = {2, 2, 2, 2, 2}, B[] = {1, 1, 1, 1, 1}  
Salida: 3

Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos posibles de los pares de elementos dados e imprimir el tamaño de ese subconjunto que satisface los criterios dados y tiene un tamaño mínimo.

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: el problema dado se puede resolver usando el enfoque codicioso , la idea es usar la clasificación y se puede observar que al elegir el i ^-ésimo par como parte del subconjunto resultante, la diferencia entre los 2 subconjuntos disminuye en la cantidad ( 2*S[i] + U[i]) . Siga los pasos a continuación para resolver el problema:

• Inicialice una array , digamos difference[] de tamaño N que almacene el valor de (2*A[i] + B[i]) para cada par de elementos.
• Inicialice una variable, digamos sum , que realiza un seguimiento de la suma de los elementos restantes de la array A[i] .
• Inicialice una variable, digamos K , que lleve la cuenta del tamaño del subconjunto resultante.
• Iterar sobre el rango [0, N) y actualizar el valor de difference[i] como el valor de (2*A[i] + B[i]) y disminuir el valor de sum por el valor A[i] .
• Ordene la diferencia de array dada [] en orden creciente .
• Recorra la array difference[] de manera inversa hasta que la suma sea negativa y agregue el valor de difference[i] a la suma e incremente el valor de K en 1 .
• Después de completar los pasos anteriores, imprima el valor de K como resultado.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum size
// of subset satisfying given criteria
void maximizeApples(vector<int>& U, vector<int>& S, int N)
{
   
    // Stores the value of 2*S[i] + U[i]
    vector<int> x(N);
 
    // Stores the difference between
    // the 2 subsets
    int sum = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Update the value of sum
        sum -= S[i];
        x[i] += 2 * S[i] + U[i];
    }
 
    // Sort the array X[] in an
    // ascending order
    sort(x.begin(), x.end());
    int ans = 0;
    int j = N - 1;
 
    // Traverse the array
    while (sum <= 0) {
 
        // Update the value of sum
        sum += x[j--];
 
        // Increment value of ans
        ans++;
    }
 
    // Print the resultant ans
    cout << ans;
}
 
// Driver Code
int main()
{
    vector<int> A = { 1, 1, 1, 1, 1 };
    vector<int> B = { 2, 2, 2, 2, 2 };
    int N = A.size();
    maximizeApples(A, B, N);
 
    return 0;
}
 
    // This code is contributed by rakeshsahni

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to find the minimum size
    // of subset satisfying given criteria
    private static void maximizeApples(
        int[] U, int[] S, int N)
    {
        // Stores the value of 2*S[i] + U[i]
        int[] x = new int[N];
 
        // Stores the difference between
        // the 2 subsets
        int sum = 0;
 
        for (int i = 0; i < N; i++) {
 
            // Update the value of sum
            sum -= S[i];
            x[i] += 2 * S[i] + U[i];
        }
 
        // Sort the array X[] in an
        // ascending order
        Arrays.sort(x);
        int ans = 0;
        int j = N - 1;
 
        // Traverse the array
        while (sum <= 0) {
 
            // Update the value of sum
            sum += x[j--];
 
            // Increment value of ans
            ans++;
        }
 
        // Print the resultant ans
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] A = new int[] { 1, 1, 1, 1, 1 };
        int[] B = new int[] { 2, 2, 2, 2, 2 };
        int N = A.length;
        maximizeApples(A, B, N);
    }
}

# Python program for the above approach
 
# Function to find the minimum size
# of subset satisfying given criteria
def maximizeApples(U, S, N):
 
    # Stores the value of 2*S[i] + U[i]
    x = [0]*N
 
    # Stores the difference between
    # the 2 subsets
    sum = 0
 
    for i in range(N):
 
        # Update the value of sum
        sum -= S[i]
        x[i] += 2 * S[i] + U[i]
 
    # Sort the array X[] in an
    # ascending order
    x.sort()
    ans = 0
    j = N - 1
 
    # Traverse the array
    while sum <= 0:
 
        # Update the value of sum
        sum += x[j]
        j = j - 1
 
        # Increment value of ans
        ans = ans + 1
 
    # Print the resultant ans
    print(ans)
 
# Driver Code
A = [1, 1, 1, 1, 1]
B = [2, 2, 2, 2, 2]
N = len(A)
maximizeApples(A, B, N)
 
# This code is contributed by Potta Lokesh

//  c# program for the above approach
using System.Collections.Generic;
using System;
class GFG
{
 
    // Function to find the minimum size
    // of subset satisfying given criteria
    static void maximizeApples(int[] U, int[] S, int N)
    {
       
        // Stores the value of 2*S[i] + U[i]
        List<int> x = new List<int>();
       
        // Stores the difference between
        // the 2 subsets
        int sum = 0;
 
        for (int i = 0; i < N; i++)
        {
           
            // Update the value of sum
            sum -= S[i];
            x.Add( 2 * S[i] + U[i]);
        }
 
        // Sort the array X[] in an
        // ascending order
        x.Sort();
        int ans = 0;
        int j = N - 1;
 
        // Traverse the array
        while (sum <= 0) {
 
            // Update the value of sum
            sum += x[j--];
 
            // Increment value of ans
            ans++;
        }
 
        // Print the resultant ans
        Console.WriteLine(ans);
    }
 
    // Driver Code
    public static void Main()
    {
        int[] A = new int[] { 1, 1, 1, 1, 1 };
        int[] B = new int[] { 2, 2, 2, 2, 2 };
        int N = A.Length;
        maximizeApples(A, B, N);
    }
}
 
// This code is contributed by amreshkumar3.

<script>
// Javascript program for the above approach
 
// Function to find the minimum size
// of subset satisfying given criteria
function maximizeApples(U, S, N) {
  // Stores the value of 2*S[i] + U[i]
  let x = new Array(N).fill(0);
 
  // Stores the difference between
  // the 2 subsets
  let sum = 0;
 
  for (let i = 0; i < N; i++) {
    // Update the value of sum
    sum -= S[i];
    x[i] += 2 * S[i] + U[i];
  }
 
  // Sort the array X[] in an
  // ascending order
  x.sort((a, b) => a - b);
 
  let ans = 0;
  let j = N - 1;
 
  // Traverse the array
  while (sum <= 0) {
    // Update the value of sum
    sum += x[j--];
 
    // Increment value of ans
    ans++;
  }
 
  // Print the resultant ans
  document.write(ans);
}
 
// Driver Code
 
let A = [1, 1, 1, 1, 1];
let B = [2, 2, 2, 2, 2];
let N = A.length;
maximizeApples(A, B, N);
 
// This code is contributed by gfgking.
</script>

3

Complejidad de tiempo: O(N*log N) 
Espacio auxiliar: O(N)