Dada una array arr[] que consta de N enteros y un entero K , la tarea es encontrar la suma de la longitud de los dos subconjuntos únicos más pequeños que tienen una suma de sus elementos de al menos K .
Ejemplos:
Entrada: arr[] = {2, 4, 5, 6, 7, 8}, K = 16
Salida: 6
Explicación:
Los subconjuntos {2, 6, 8} y {4, 5, 7} son los dos subconjuntos más pequeños con suma K(= 16).
Por lo tanto, la suma de las longitudes de estos dos subconjuntos = 3 + 3 = 6.Entrada: arr[] = {14, 3, 7, 8, 9, 7, 12, 15, 10, 6}, K = 40
Salida: 8
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Ordenar el arreglo reduce el problema a elegir un subarreglo cuya suma sea al menos K entre el rango de índices [i, N] , y luego verifique si la suma de los elementos restantes del arreglo en el rango de índices [i, N] es K o no.
- Para implementar la idea anterior, se usa una array 2D , digamos dp[][] , tal que dp[i][j] almacena la suma mínima del subconjunto sobre el rango de índices [i, N] que tiene un valor de al menos j. Entonces el estado de transición es similar a 0/1 Mochila que se puede definir como:
- Si el valor de arr[i] es mayor que j , actualice dp[i][j] a arr[i] .
- De lo contrario, actualice dp[i][j] al mínimo de dp[i + 1][j] y (dp[i + 1][j – arr[i]] + arr[i]) .
Siga los pasos a continuación para resolver el problema:
- Ordene la array en orden ascendente .
- Inicialice una array, diga sufijo [], y almacene la suma del sufijo de la array arr [] en ella.
- Inicialice una array 2D , digamos dp[][], de modo que dp[i][j] almacene la suma mínima del subconjunto sobre el rango de índices [i, N] que tengan un valor de al menos j .
- Inicialice dp[N][0] como 0 y todos los demás estados como INT_MAX .
- Recorra la array arr[i] en orden inverso y realice los siguientes pasos:
- Itere sobre el rango de índices [0, K] en orden inverso y realice las siguientes operaciones:
- Si el valor de arr[i] es al menos j , actualice el valor de dp[i][j] como arr[i] ya que el estado actual tiene suma al menos j . Ahora, continúa la iteración .
- Si el valor del siguiente estado, es decir, dp[i + 1][j – arr[i]] es INT_MAX , entonces actualice dp[i][j] como INT_MAX .
- De lo contrario, actualice dp[i][j] como el mínimo de dp[i + 1][j] y (dp[i + 1][j – arr[i]] + arr[i]) para almacenar la suma de todos los valores que tienen suma al menos j .
- Itere sobre el rango de índices [0, K] en orden inverso y realice las siguientes operaciones:
- Ahora, recorra el sufijo del arreglo[] en orden inverso y si el valor de (sufijo[i] – dp[i][K]) es al menos K , entonces imprima (N – i) como la suma del tamaño del dos subconjuntos más pequeños formados y salen del bucle .
- De lo contrario, imprima “-1” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e9;
// Function to calculate sum of lengths
// of two smallest subsets with sum >= K
int MinimumLength(int A[], int N, int K)
{
// Sort the array in ascending order
sort(A, A + N);
// Stores suffix sum of the array
int suffix[N + 1] = { 0 };
// Update the suffix sum array
for (int i = N - 1; i >= 0; i--)
suffix[i] = suffix[i + 1] + A[i];
// Stores all dp-states
int dp[N + 1][K + 1];
// Initialize all dp-states
// with a maximum possible value
for (int i = 0; i <= N; i++)
for (int j = 0; j <= K; j++)
dp[i][j] = MAX;
// Base Case
dp[N][0] = 0;
// Traverse the array arr[]
for (int i = N - 1; i >= 0; i--) {
// Iterate over the range [0, K]
for (int j = K; j >= 0; j--) {
// If A[i] is equal to at
// least the required sum
// j for the current state
if (j <= A[i]) {
dp[i][j] = A[i];
continue;
}
// If the next possible
// state doesn't exist
if (dp[i + 1][j - A[i]] == MAX)
dp[i][j] = MAX;
// Otherwise, update the current
// state to the minimum of the
// next state and state including
// the current element A[i]
else
dp[i][j] = min(dp[i + 1][j],
dp[i + 1][j - A[i]] + A[i]);
}
}
// Traverse the suffix sum array
for (int i = N - 1; i >= 0; i--) {
// If suffix[i] - dp[i][K] >= K
if (suffix[i] - dp[i][K] >= K) {
// Sum of lengths of the two
// smallest subsets is obtained
return N - i;
}
}
// Return -1, if there doesn't
// exist any subset of sum >= K
return -1;
}
// Driver Code
int main()
{
int arr[] = { 7, 4, 5, 6, 8 };
int K = 13;
int N = sizeof(arr) / sizeof(arr[0]);
cout << MinimumLength(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
static int MAX = (int)(1e9);
// Function to calculate sum of lengths
// of two smallest subsets with sum >= K
static int MinimumLength(int A[], int N, int K)
{
// Sort the array in ascending order
Arrays.sort(A);
// Stores suffix sum of the array
int suffix[] = new int[N + 1];
// Update the suffix sum array
for(int i = N - 1; i >= 0; i--)
suffix[i] = suffix[i + 1] + A[i];
// Stores all dp-states
int dp[][] = new int[N + 1][K + 1];
// Initialize all dp-states
// with a maximum possible value
for(int i = 0; i <= N; i++)
for(int j = 0; j <= K; j++)
dp[i][j] = MAX;
// Base Case
dp[N][0] = 0;
// Traverse the array arr[]
for(int i = N - 1; i >= 0; i--)
{
// Iterate over the range [0, K]
for(int j = K; j >= 0; j--)
{
// If A[i] is equal to at
// least the required sum
// j for the current state
if (j <= A[i])
{
dp[i][j] = A[i];
continue;
}
// If the next possible
// state doesn't exist
if (dp[i + 1][j - A[i]] == MAX)
dp[i][j] = MAX;
// Otherwise, update the current
// state to the minimum of the
// next state and state including
// the current element A[i]
else
dp[i][j] = Math.min(dp[i + 1][j],
dp[i + 1][j - A[i]]
+ A[i]);
}
}
// Traverse the suffix sum array
for(int i = N - 1; i >= 0; i--)
{
// If suffix[i] - dp[i][K] >= K
if (suffix[i] - dp[i][K] >= K)
{
// Sum of lengths of the two
// smallest subsets is obtained
return N - i;
}
}
// Return -1, if there doesn't
// exist any subset of sum >= K
return -1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 7, 4, 5, 6, 8 };
int K = 13;
int N = arr.length;
System.out.println(MinimumLength(arr, N, K));
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach MAX = 1e9 # Function to calculate sum of lengths # of two smallest subsets with sum >= K def MinimumLength(A, N, K): # Sort the array in ascending order A.sort() # Stores suffix sum of the array suffix = [0] * (N + 1) # Update the suffix sum array for i in range(N - 1, -1, -1): suffix[i] = suffix[i + 1] + A[i] # Stores all dp-states dp = [[0] * (K + 1)] * (N + 1) # Initialize all dp-states # with a maximum possible value for i in range(N + 1): for j in range(K + 1): dp[i][j] = MAX # Base Case dp[N][0] = 0 # Traverse the array arr[] for i in range(N - 1, -1, -1): # Iterate over the range [0, K] for j in range(K, -1, -1): # If A[i] is equal to at # least the required sum # j for the current state if (j <= A[i]) : dp[i][j] = A[i] continue # If the next possible # state doesn't exist if (dp[i + 1][j - A[i]] == MAX): dp[i][j] = MAX # Otherwise, update the current # state to the minimum of the # next state and state including # the current element A[i] else : dp[i][j] = min(dp[i + 1][j], dp[i + 1][j - A[i]] + A[i]) # Traverse the suffix sum array for i in range(N - 1, -1, -1): # If suffix[i] - dp[i][K] >= K if (suffix[i] - dp[i][K] >= K): # Sum of lengths of the two # smallest subsets is obtained return N - i # Return -1, if there doesn't # exist any subset of sum >= K return -1 # Driver Code arr = [ 7, 4, 5, 6, 8 ] K = 13 N = len(arr) print(MinimumLength(arr, N, K)) # This code is contributed by splevel62
C#
// C# program for the above approach
using System;
class GFG{
static int MAX = (int)(1e9);
// Function to calculate sum of lengths
// of two smallest subsets with sum >= K
static int MinimumLength(int[] A, int N, int K)
{
// Sort the array in ascending order
Array.Sort(A);
// Stores suffix sum of the array
int[] suffix = new int[N + 1];
// Update the suffix sum array
for(int i = N - 1; i >= 0; i--)
suffix[i] = suffix[i + 1] + A[i];
// Stores all dp-states
int[,] dp = new int[N + 1, K + 1];
// Initialize all dp-states
// with a maximum possible value
for(int i = 0; i <= N; i++)
for(int j = 0; j <= K; j++)
dp[i, j] = MAX;
// Base Case
dp[N, 0] = 0;
// Traverse the array arr[]
for(int i = N - 1; i >= 0; i--)
{
// Iterate over the range [0, K]
for(int j = K; j >= 0; j--)
{
// If A[i] is equal to at
// least the required sum
// j for the current state
if (j <= A[i])
{
dp[i, j] = A[i];
continue;
}
// If the next possible
// state doesn't exist
if (dp[i + 1, j - A[i]] == MAX)
dp[i, j] = MAX;
// Otherwise, update the current
// state to the minimum of the
// next state and state including
// the current element A[i]
else
dp[i, j] = Math.Min(dp[i + 1, j],
dp[i + 1, j - A[i]]
+ A[i]);
}
}
// Traverse the suffix sum array
for(int i = N - 1; i >= 0; i--)
{
// If suffix[i] - dp[i][K] >= K
if (suffix[i] - dp[i, K] >= K)
{
// Sum of lengths of the two
// smallest subsets is obtained
return N - i;
}
}
// Return -1, if there doesn't
// exist any subset of sum >= K
return -1;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 7, 4, 5, 6, 8 };
int K = 13;
int N = arr.Length;
Console.WriteLine(MinimumLength(arr, N, K));
}
}
// This code is contributed by ukasp
Javascript
<script>
// javascript program for the above approach
var max1 = 1000000000;
// Function to calculate sum of lengths
// of two smallest subsets with sum >= K
function MinimumLength(A, N, K)
{
0
// Sort the array in ascending order
A.sort();
// Stores suffix sum of the array
var suffix = Array(N + 1).fill(0);
var i;
// Update the suffix sum array
for (i = N - 1; i >= 0; i--)
suffix[i] = suffix[i + 1] + A[i];
// Stores all dp-states
var dp = new Array(N + 1);
for (i = 0; i < N+1; i++)
dp[i] = new Array(K + 1);
// Initialize all dp-states
// with a max1imum possible value
var j;
for (i = 0; i <= N; i++) {
for (j = 0; j <= K; j++){
dp[i][j] = max1;
}
};
// Base Case
dp[N][0] = 0;
// Traverse the array arr[]
for (i = N - 1; i >= 0; i--) {
// Iterate over the range [0, K]
for (j = K; j >= 0; j--) {
// If A[i] is equal to at
// least the required sum
// j for the current state
if (j <= A[i]) {
dp[i][j] = A[i];
continue;
}
// If the next possible
// state doesn't exist
if (dp[i + 1][j - A[i]] == max1)
dp[i][j] = max1;
// Otherwise, update the current
// state to the minimum of the
// next state and state including
// the current element A[i]
else
dp[i][j] = Math.min(dp[i + 1][j],
dp[i + 1][j - A[i]] + A[i]);
}
}
// Traverse the suffix sum array
for (i = N - 1; i >= 0; i--) {
// If suffix[i] - dp[i][K] >= K
if (suffix[i] - dp[i][K] >= K) {
// Sum of lengths of the two
// smallest subsets is obtained
return N - i;
}
}
// Return -1, if there doesn't
// exist any subset of sum >= K
return -1;
}
// Driver Code
var arr = [7, 4, 5, 6, 8];
var K = 13;
var N = arr.length;
document.write(MinimumLength(arr, N, K));
// This code is contributed by SURENDRA_GANGWAR.
</script>
Producción:
4
Complejidad temporal: O(N * K)
Espacio auxiliar: O(N * K)