Subconjunto más grande con suma menor que cada elemento de array

Dado un arreglo arr[] que contiene N elementos, la tarea es encontrar el tamaño del subconjunto más grande para cada elemento del arreglo arr[i] tal que la suma del subconjunto sea menor que ese elemento.

Ejemplos:

Entrada: arr[] = { 5, 2, 1, 1, 1, 6, 8}
Salida: 3 1 0 0 0 4 4 +
Explicación: 
Para i = 0 -> subconjunto = {1, 1, 1}, suma = 3. Ningún otro subconjunto mayor tiene una suma menor que 5.
Para i = 1 -> subconjunto = {1}. Suma = 1 que es menor que arr[1] = 2
Para i = 2 -> subconjunto = {}. Ningún elemento con valor inferior a 1 presente en la array.
Para i = 3 e i = 4, los subconjuntos tampoco tendrán ningún elemento.
Para i = 5 -> subconjunto = {2, 1, 1, 1}, sum = 5 que es menor que arr[5] = 6 y de mayor tamaño.
Para i = 6 -> subconjunto = {2, 1, 1, 1}, sum = 5 que es menor que arr[6] = 8 y de mayor tamaño.

Entrada: arr[] = { 2, 1, 4, 5, 3, 2, 1 }
Salida: 1 0 2 3 2 1 0 

Enfoque ingenuo: la forma más sencilla de resolver el problema es formar todos los subconjuntos para cada arr[i] y encontrar el más grande con una suma menor que ese elemento entre todos los subconjuntos.

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

Mejor enfoque : un mejor enfoque para resolver el problema es usar el método Greedy basado en la siguiente idea. 

Haga una copia de la array real y ordene el duplicado cada vez más. Después de eso, para cada elemento de la array (arr[i]), recorra la array duplicada y encuentre el máximo de cuántos elementos desde el principio se pueden agregar a un subconjunto de modo que la suma sea menor que arr[i].

Siga los pasos que se mencionan a continuación para resolver el problema:

• Haga una copia (digamos v ) de la array.
• Ordena el duplicado en orden creciente.
• Atraviesa la array de i = 0 a N-1 :
  • Para cada elemento, recorra desde el inicio del duplicado y:
    • Compruebe si agregar el elemento actual del duplicado mantiene la suma menor que arr[i] o no.
    • Si la suma excede arr[i] , rompa el bucle.
    • De lo contrario, recorre el bucle y aumenta el tamaño del subconjunto.
  • Agregue el tamaño del subconjunto a la array de resultados.
• Devuelve la array de resultados.

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

// C++ code to implement above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find out the largest subset
// for each array element
vector<int> max_subset(int a[], int n)
{
    // Making another copy of array
    vector<int> v, ans;
    for (int i = 0; i < n; i++)
        v.push_back(a[i]);
 
    // Sorting the vector
    sort(v.begin(), v.end());
 
    // Iterating over every elements
    // of the array
    for (int i = 0; i < n; i++) {
 
        // Finding the maximum number
        // of elements whose sum
        // is less than a[i]
        int sum = 0, maxi = 0;
        for (int j = 0; j < n; j++) {
            sum += v[j];
            if (sum >= a[i]) {
                maxi = j;
                break;
            }
        }
        ans.push_back(maxi);
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 5, 2, 1, 1, 1, 6, 8 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    vector<int> ans = max_subset(arr, N);
    for (int x : ans)
        cout << x << " ";
    return 0;
}

// Java implementation of above approach
import java.io.*;
import java.util.*;
 
class GFG {
 
  // Function to find out the largest subset
  // for each array element
  static ArrayList<Integer> max_subset(int[] a, int n)
  {
 
    // Making another copy of array
    ArrayList<Integer> v = new ArrayList<Integer>();
    ArrayList<Integer> ans = new ArrayList<Integer>();
    for (int i = 0; i < n; i++)
      v.add(a[i]);
 
    // Sorting the vector
    Collections.sort(v);
 
    // Iterating over every elements
    // of the array
    for (int i = 0; i < n; i++) {
 
      // Finding the maximum number
      // of elements whose sum
      // is less than a[i]
      int sum = 0, maxi = 0;
      for (int j = 0; j < n; j++) {
        sum += (int)v.get(j);
        if (sum >= a[i]) {
          maxi = j;
          break;
        }
      }
      ans.add(maxi);
    }
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] arr = { 5, 2, 1, 1, 1, 6, 8 };
    int N = arr.length;
 
    // Function call
    ArrayList<Integer> ans = max_subset(arr, N);
    for(int x : ans)
      System.out.print(x + " ");
 
  }
}
 
// This code is contributed by sanjoy_62.

# Python3 code to implement the above approach
 
# function to find the largest subset for each
# array element
def max_subset(a, n):
   
    # making a copy if a
    v = a.copy()
 
    ans = []
     
    # sorting v
    v.sort()
     
    # iterating over a
    for i in range(n):
       
        # finding the max number of elements
        # whose sum is less than a[i]
        sums = 0
        maxi = 0
        for j in range(n):
            sums += v[j]
            if sums >= a[i]:
                maxi = j
                break
        ans.append(maxi)
    return ans
 
# Driver Code
arr = [5, 2, 1, 1, 1, 6, 8]
N = len(arr)
 
# Function call
ans = max_subset(arr, N)
print(" ".join(list(map(str, ans))))
 
# This code is contributed by phasing7.

// C# code to implement above approach
using System;
using System.Collections;
 
class GFG {
 
  // Function to find out the largest subset
  // for each array element
  static ArrayList max_subset(int[] a, int n)
  {
     
    // Making another copy of array
    ArrayList v = new ArrayList();
    ArrayList ans = new ArrayList();
    for (int i = 0; i < n; i++)
      v.Add(a[i]);
 
    // Sorting the vector
    v.Sort();
 
    // Iterating over every elements
    // of the array
    for (int i = 0; i < n; i++) {
 
      // Finding the maximum number
      // of elements whose sum
      // is less than a[i]
      int sum = 0, maxi = 0;
      for (int j = 0; j < n; j++) {
        sum += (int)v[j];
        if (sum >= a[i]) {
          maxi = j;
          break;
        }
      }
      ans.Add(maxi);
    }
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int[] arr = { 5, 2, 1, 1, 1, 6, 8 };
    int N = arr.Length;
 
    // Function call
    ArrayList ans = max_subset(arr, N);
    foreach(int x in ans) Console.Write(x + " ");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
 
       // Function to find out the largest subset
       // for each array element
       function max_subset(a, n) {
           // Making another copy of array
           let v = [], ans = [];
           for (let i = 0; i < n; i++)
               v.push(a[i]);
 
           // Sorting the vector
           v.sort();
 
           // Iterating over every elements
           // of the array
           for (let i = 0; i < n; i++) {
 
               // Finding the maximum number
               // of elements whose sum
               // is less than a[i]
               let sum = 0, maxi = 0;
               for (let j = 0; j < n; j++) {
                   sum += v[j];
                   if (sum >= a[i]) {
                       maxi = j;
                       break;
                   }
               }
               ans.push(maxi);
           }
           return ans;
       }
 
       // Driver code
       let arr = [5, 2, 1, 1, 1, 6, 8];
       let N = arr.length;
 
       // Function call
       let ans = max_subset(arr, N);
       for (let x of ans)
           document.write(x + " ")
 
    // This code is contributed by Potta Lokesh
   </script>

3 1 0 0 0 4 4 

Complejidad temporal : O(N ² )
Espacio auxiliar : O(N)

Enfoque eficiente: el enfoque eficiente es similar al enfoque anterior pero utiliza el concepto de suma de prefijos y límite inferior como se menciona aquí;

Después de ordenar la array duplicada, cree una array de suma de prefijos de la array duplicada. 
Para cada elemento, en lugar de iterar la array duplicada, use el límite inferior en la array de suma de prefijos para encontrar la cantidad de elementos que se pueden incluir en un subconjunto.

Siga los pasos que se mencionan a continuación:

• Cree una array duplicada y ordene el duplicado (digamos v ).
• Cree una array de prefijos para v .
• Iterar de i = 0 a N-1 en arr[]:
  • Use el límite inferior en la array de prefijos y encuentre cuántos elementos se pueden incluir en el subconjunto.
  • Agregue el tamaño del subconjunto en la array de resultados.
• Devuelve la array de resultados.

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

// C++ code to implement above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest subset
// with sum less than arr[i]
vector<int> max_subset(int a[], int n)
{
    // Making another copy of array
    vector<int> v, ans;
    for (int i = 0; i < n; i++)
        v.push_back(a[i]);
 
    // Sorting the vector
    sort(v.begin(), v.end());
 
    // Prefix sum array
    int pref[n];
    pref[0] = v[0];
    for (int i = 1; i < n; i++)
        pref[i] = pref[i - 1] + v[i];
 
    // Iterating over every elements
    // of the array
    for (int i = 0; i < n; i++) {
 
        // Using prefix array and
        // lower_bound() function for
        // finding the maximum number
        // of elements
        auto it
            = lower_bound(pref,
                          pref + n, a[i]);
 
        int maxi = it - pref;
        ans.push_back(maxi);
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 5, 2, 1, 1, 1, 6, 8 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    vector<int> ans = max_subset(arr, N);
    for (int x : ans)
        cout << x << " ";
    return 0;
}

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
    static int lower_bound(int arr[], int x){
        int n = arr.length;
        int l = 0, r = n, ans = n, mid;
        while(l <= r){
            mid = (l + r)/2;
            if(arr[mid] >= x){
                ans = mid;
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return ans;
    }
 
    // Function to find the largest subset
    // with sum less than arr[i]
    static ArrayList<Integer> max_subset(int a[], int n)
    {
        // Making another copy of array
        ArrayList<Integer> v = new ArrayList<Integer>();
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for (int i = 0 ; i < n ; i++){
            v.add(a[i]);
        }
 
        // Sorting the vector
        Collections.sort(v);
 
        // Prefix sum array
        int pref[] = new int[n];
        pref[0] = v.get(0);
        for (int i = 1 ; i < n ; i++){
            pref[i] = pref[i - 1] + v.get(i);
        }
 
        // Iterating over every elements
        // of the array
        for (int i = 0 ; i < n ; i++) {
 
            // Using prefix array and
            // lower_bound() function for
            // finding the maximum number
            // of elements
            int it = lower_bound(pref, a[i]);
 
            int maxi = it;
            ans.add(maxi);
        }
        return ans;
    }
 
    public static void main(String args[])
    {
        int arr[] = new int[]{
            5, 2, 1, 1, 1, 6, 8
        };
        int N = arr.length;
 
        // Function call
        ArrayList<Integer> ans = max_subset(arr, N);
        for(int i = 0 ; i < ans.size() ; i++){
            System.out.print(ans.get(i) + " ");
        }
    }
}
 
// This code is contributed by subhamgoyal2014.

# Python3 code to implement the above approach
from bisect import bisect_left
 
# Function to find the largest subset
# with sum less than arr[i]
def max_subset(a, n):
   
    # making another copy of the array
    v = a.copy()
    ans = []
 
    # sorting v
    v.sort()
    # prefix sum array
    pref = [v[0]]
    for i in range(n - 1):
        pref.append(pref[i] + v[i + 1])
    # iterating over ever element
    # of the array
    for i in range(n):
       
        # using prefix array and bisect_left() Function
        # for finding the max number of elements
        # bisect_left(pref, a[i]) returns the rightmost element
        # greater than or equal to a[i]
        it = bisect_left(pref, a[i])
        maxi = it
        ans.append(maxi)
    return ans
 
 
# Driver Code
arr = [5, 2, 1, 1, 1, 6, 8]
N = len(arr)
print(" ".join(map(str, max_subset(arr, N))))
 
# This code is contributed by phasing17.

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
 
    static int lower_bound(int []arr, int x){
        int n = arr.Length;
        int l = 0, r = n, ans = n, mid;
        while(l <= r){
            mid = (l + r)/2;
            if(arr[mid] >= x){
                ans = mid;
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return ans;
    }
 
    // Function to find the largest subset
    // with sum less than arr[i]
    static List<int> max_subset(int []a, int n)
    {
        // Making another copy of array
        List<int> v = new List<int>();
        List<int> ans = new List<int>();
        for (int i = 0 ; i < n ; i++){
            v.Add(a[i]);
        }
 
        // Sorting the vector
        v.Sort();
 
        // Prefix sum array
        int []pref = new int[n];
        pref[0] = v[0];
        for (int i = 1 ; i < n ; i++){
            pref[i] = pref[i - 1] + v[i];
        }
 
        // Iterating over every elements
        // of the array
        for (int i = 0 ; i < n ; i++) {
 
            // Using prefix array and
            // lower_bound() function for
            // finding the maximum number
            // of elements
            int it = lower_bound(pref, a[i]);
 
            int maxi = it;
            ans.Add(maxi);
        }
        return ans;
    }
 
    public static void Main(String []args)
    {
        int []arr = new int[]{
            5, 2, 1, 1, 1, 6, 8
        };
        int N = arr.Length;
 
        // Function call
        List<int> ans = max_subset(arr, N);
        for(int i = 0 ; i < ans.Count ; i++){
            Console.Write(ans[i] + " ");
        }
    }
}
 
// This code contributed by shikhasingrajput

<script>
       // JavaScript code for the above approach
 
       // Function to find out the largest subset
       // for each array element
       function max_subset(a, n)
       {
        
           // Making another copy of array
           let v = [], ans = [];
           for (let i = 0; i < n; i++)
               v.push(a[i]);
 
           // Sorting the vector
           v.sort();
 
           // Iterating over every elements
           // of the array
           for (let i = 0; i < n; i++) {
 
               // Finding the maximum number
               // of elements whose sum
               // is less than a[i]
               let sum = 0, maxi = 0;
               for (let j = 0; j < n; j++) {
                   sum += v[j];
                   if (sum >= a[i]) {
                       maxi = j;
                       break;
                   }
               }
               ans.push(maxi);
           }
           return ans;
       }
 
       // Driver code
       let arr = [5, 2, 1, 1, 1, 6, 8];
       let N = arr.length;
 
       // Function call
       let ans = max_subset(arr, N);
       for (let x of ans)
           document.write(x + " ")
            
           // This code is contributed by code_hunt.
   </script>

3 1 0 0 0 4 4 

Complejidad temporal: O(N * log(N))
Espacio auxiliar: O(N)