Dados dos arreglos A[] y B[] que consisten en N enteros positivos, la tarea es encontrar el número total de subconjuntos de índices tales que el valor máximo en el arreglo A[] sobre todos estos índices sea mayor o igual que el suma de todos los valores sobre estos índices en la array B[] .
Ejemplos:
Entrada: A[] = {3, 1}, B[] = {1, 2}
Salida: 2
Explicación:
El total de subconjuntos de índices válidos posibles son {0}, {0, 1}
{0}: max(3 ) >= suma(1)
{1, 2}: max(1, 3) >= suma(1, 2)Entrada: A[] = {1, 3, 2, 6}, B[] = {7, 3, 2, 1}
Salida: 6
Enfoque: el problema anterior se puede resolver usando el concepto discutido en el problema de la suma de subconjuntos con la ayuda de la programación dinámica . La idea es crear un dp[][] de dimensiones N * elemento máximo de la array A[] . Ahora, cada Node de la array dp[][] , es decir, dp[i][j] representa el número de subconjuntos de los primeros i elementos que tienen suma j . Siga los pasos a continuación para resolver este problema:
- Cree una variable, digamos ans como 0 para almacenar el número total de subconjuntos requeridos.
- Cree un vector de pares , digamos AB , y llénelo con los elementos de A y B, es decir, AB[i] = {A[i], B[i]} .
- Ordene este vector de pares sobre la base del primer elemento .
- Inicialmente, la tabla dp se llenará con ceros excepto dp[0][0] = 1 .
- Recorra la array AB[] y considere el valor de AB[i].primero como el máximo porque AB se ordena en el primer elemento y es máximo en el rango [0, i] y en cada iteración, recorre todas las sumas posibles j y para cada iteración calcule los subconjuntos hasta el índice i que tenga la suma j incluyendo y excluyendo el elemento actual.
- Después de completar los pasos anteriores, recorra la array dp[][] y verifique cuántos subconjuntos formados son válidos al verificar las siguientes condiciones. Si se determina que es verdadero , agregue el valor dp[i – 1][j] a la variable ans .
j + AB[i – 1].segundo <= AB[i].primero
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
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;
// Function to find the number of non-empty
// subset of indices such that the maximum
// of values over these indices in A is
// at least the total sum over B[]
int countValidSubsets(int A[], int B[], int N)
{
int ans = 0;
vector<pair<int, int> > AB(N);
// Stores the maximum element in
// the array A[]
int mx = INT_MIN;
// Do the DP in 1-based indexing
// as there will be no corner case
// to handle specifically
for (int i = 0; i <= N; i++) {
AB[i] = { A[i], B[i] };
mx = max(mx, A[i]);
}
// Sort the pair vector
sort(AB.begin(), AB.end());
// dp matrix where dp[i][j] denotes
// total valid subsets upto index
// i with sum j
vector<vector<int> > dp(
N + 1, vector<int>(mx + 1, 0));
dp[0][0] = 1;
// Traverse the array AB[]
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= mx; j++) {
// Selecting the current
// element in the subset
if (j + AB[i - 1].second <= mx) {
dp[i][j + AB[i - 1].second]
+= dp[i - 1][j];
}
// Discarding the element
dp[i][j] += dp[i - 1][j];
}
}
// Take the count of valid subsets
for (int i = 1; i <= N; ++i) {
int cnt = 0;
// Iterate through all the
// possible subsets
for (int j = 0; j <= mx; j++) {
// Check if the current subsets
// till index i having sum j
// are valid
if (j + AB[i - 1].second
<= AB[i - 1].first) {
cnt += dp[i - 1][j];
}
}
// Update the value of ans
ans += cnt;
}
// Return the total count of subsets
return ans;
}
// Driver Code
int main()
{
int A[] = { 1, 3, 2, 6 };
int B[] = { 7, 3, 2, 1 };
int N = sizeof(A) / sizeof(A[0]);
cout << countValidSubsets(A, B, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to find the number of non-empty
// subset of indices such that the maximum
// of values over these indices in A is
// at least the total sum over B[]
static int countValidSubsets(int A[], int B[], int N)
{
int ans = 0;
pair []AB = new pair[N];
// Stores the maximum element in
// the array A[]
int mx = Integer.MIN_VALUE;
// Do the DP in 1-based indexing
// as there will be no corner case
// to handle specifically
for (int i = 0; i < N; i++) {
AB[i] = new pair( A[i], B[i] );
mx = Math.max(mx, A[i]);
}
// Sort the pair vector
Arrays.sort(AB,(a,b)->a.first-b.first);
// dp matrix where dp[i][j] denotes
// total valid subsets upto index
// i with sum j
int[][] dp= new int[N + 1][mx + 1];
dp[0][0] = 1;
// Traverse the array AB[]
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= mx; j++) {
// Selecting the current
// element in the subset
if (j + AB[i - 1].second <= mx) {
dp[i][j + AB[i - 1].second]
+= dp[i - 1][j];
}
// Discarding the element
dp[i][j] += dp[i - 1][j];
}
}
// Take the count of valid subsets
for (int i = 1; i <= N; ++i) {
int cnt = 0;
// Iterate through all the
// possible subsets
for (int j = 0; j <= mx; j++) {
// Check if the current subsets
// till index i having sum j
// are valid
if (j + AB[i - 1].second
<= AB[i - 1].first) {
cnt += dp[i - 1][j];
}
}
// Update the value of ans
ans += cnt;
}
// Return the total count of subsets
return ans;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 3, 2, 6 };
int B[] = { 7, 3, 2, 1 };
int N = A.length;
System.out.print(countValidSubsets(A, B, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# python program for the above approach INT_MIN = -2147483648 # Function to find the number of non-empty # subset of indices such that the maximum # of values over these indices in A is # at least the total sum over B[] def countValidSubsets(A, B, N): ans = 0 AB = [[0 for _ in range(2)] for _ in range(N)] # Stores the maximum element in # the array A[] mx = INT_MIN # Do the DP in 1-based indexing # as there will be no corner case # to handle specifically for i in range(0, N): AB[i] = [A[i], B[i]] mx = max(mx, A[i]) # Sort the pair vector AB.sort() # dp matrix where dp[i][j] denotes # total valid subsets upto index # i with sum j dp = [[0 for _ in range(mx+1)] for _ in range(N+1)] dp[0][0] = 1 # Traverse the array AB[] for i in range(1, N+1): for j in range(0, mx+1): # Selecting the current # element in the subset if (j + AB[i - 1][1] <= mx): dp[i][j + AB[i - 1][1]] += dp[i - 1][j] # Discarding the element dp[i][j] += dp[i - 1][j] # Take the count of valid subsets for i in range(1, N+1): cnt = 0 # Iterate through all the # possible subsets for j in range(0, mx+1): # Check if the current subsets # till index i having sum j # are valid if (j + AB[i - 1][1] <= AB[i - 1][0]): cnt += dp[i - 1][j] # Update the value of ans ans += cnt # Return the total count of subsets return ans # Driver Code if __name__ == "__main__": A = [1, 3, 2, 6] B = [7, 3, 2, 1] N = len(A) print(countValidSubsets(A, B, N)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Linq;
public class GFG{
class pair : IComparable<pair>
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
public int CompareTo(pair p)
{
return this.first-p.second;
}
}
// Function to find the number of non-empty
// subset of indices such that the maximum
// of values over these indices in A is
// at least the total sum over []B
static int countValidSubsets(int []A, int []B, int N)
{
int ans = 0;
pair []AB = new pair[N];
// Stores the maximum element in
// the array []A
int mx = int.MinValue;
// Do the DP in 1-based indexing
// as there will be no corner case
// to handle specifically
for (int i = 0; i < N; i++) {
AB[i] = new pair( A[i], B[i] );
mx = Math.Max(mx, A[i]);
}
// Sort the pair vector
Array.Sort(AB);
AB.Reverse();
// dp matrix where dp[i,j] denotes
// total valid subsets upto index
// i with sum j
int[,] dp= new int[N + 1,mx + 1];
dp[0,0] = 1;
// Traverse the array AB[]
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= mx; j++) {
// Selecting the current
// element in the subset
if (j + AB[i - 1].second <= mx) {
dp[i,j + AB[i - 1].second]
+= dp[i - 1,j];
}
// Discarding the element
dp[i,j] += dp[i - 1,j];
}
}
// Take the count of valid subsets
for (int i = 1; i <= N; ++i) {
int cnt = 0;
// Iterate through all the
// possible subsets
for (int j = 0; j <= mx; j++) {
// Check if the current subsets
// till index i having sum j
// are valid
if (j + AB[i - 1].second
<= AB[i - 1].first) {
cnt += dp[i - 1,j];
}
}
// Update the value of ans
ans += cnt;
}
// Return the total count of subsets
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []A = { 1, 3, 2, 6 };
int []B = { 7, 3, 2, 1 };
int N = A.Length;
Console.Write(countValidSubsets(A, B, N));
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of non-empty
// subset of indices such that the maximum
// of values over these indices in A is
// at least the total sum over B[]
function countValidSubsets(A, B, N) {
let ans = 0;
let AB = new Array(N);
// Stores the maximum element in
// the array A[]
let mx = Number.MIN_SAFE_INTEGER;
// Do the DP in 1-based indexing
// as there will be no corner case
// to handle specifically
for (let i = 0; i < N; i++) {
AB[i] = [A[i], B[i]];
mx = Math.max(mx, A[i]);
console.log(A[i]);
}
// Sort the pair vector
AB.sort((a, b) => a - b);
// dp matrix where dp[i][j] denotes
// total valid subsets upto index
// i with sum j
let dp = new Array(N + 1).fill(0).map(() => {
return new Array(mx + 1).fill(0);
});
dp[0][0] = 1;
// Traverse the array AB[]
for (let i = 1; i <= N; i++)
{
for (let j = 0; j <= mx; j++)
{
// Selecting the current
// element in the subset
if (j + AB[i - 1][1] <= mx) {
dp[i][j + AB[i - 1][1]] += dp[i - 1][j];
}
// Discarding the element
dp[i][j] += dp[i - 1][j];
}
}
// Take the count of valid subsets
for (let i = 1; i <= N; ++i)
{
let cnt = 0;
// Iterate through all the
// possible subsets
for (let j = 0; j <= mx; j++)
{
// Check if the current subsets
// till index i having sum j
// are valid
if (j + AB[i - 1][1] <= AB[i - 1][0]) {
cnt += dp[i - 1][j];
}
}
// Update the value of ans
ans += cnt;
}
// Return the total count of subsets
return ans;
}
// Driver Code
let A = [1, 3, 2, 6];
let B = [7, 3, 2, 1];
let N = A.length;
document.write(countValidSubsets(A, B, N));
// This code is contributed by gfgking.
</script>
Producción:
6
Complejidad de tiempo: O(N*M), donde M es el elemento máximo de la array .
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA