Dados dos arreglos A[] y B[] que consisten en N y M enteros respectivamente, y un entero K , la tarea es encontrar la suma más cercana posible a K seleccionando exactamente un elemento del arreglo A[] y un elemento del array B[] , como máximo dos veces .
Ejemplos:
Entrada: A[] = {1, 7}, B[] = {3, 4}, K = 10
Salida: 10
Explicación:
Suma obtenida al seleccionar A[0] y A[1] = 3 + 7 = 10, que está más cerca del valor K(= 10).Entrada: A[] = {2, 3}, B[] = {4, 5, 30}, K = 18
Salida: 17
Enfoque: El problema dado se puede resolver usando la recursividad , encontrando la suma de los elementos de los subconjuntos de la array B[] que tengan la suma más cercana a (K – A[i]) para cada elemento de la array A[i] . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos mini como INT_MAX y ans como INT_MAX para almacenar la diferencia absoluta mínima y el valor más cercano a K .
- Defina una función recursiva , diga findClosest(arr, i, currSum) para encontrar la suma del subconjunto de la array más cercana a K , donde i es el índice en la array B[] y currSum almacena la suma del subconjunto.
- Si el valor de i es al menos M , entonces regrese de la función.
- Si el valor absoluto de (currSum – K) es menor que mini , actualice el valor de mini como abs(currSum – K) y actualice el valor de ans como currSum .
- Si el valor absoluto de (currSum – K) es igual a mini entonces, actualice el valor de ans como el mínimo de ans y currSum .
- Llame a la función recursiva excluyendo el elemento B[i] como findClosest(i + 1, currSum) .
- Llame a la función recursiva que incluye el elemento B[i] una vez como findClosest(i + 1, currSum + B[i]) .
- Llame a la función recursiva que incluye el elemento B[i] dos veces como findClosest(i + 1, currSum + 2*B[i]) .
- Recorra la array dada A[] y para cada elemento llame a la función findClosest(0, A[i]) .
- Después de completar los pasos anteriores, imprima el valor de ans como la suma resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Stores the sum closest to K
int ans = INT_MAX;
// Stores the minimum absolute difference
int mini = INT_MAX;
// Function to choose the elements
// from the array B[]
void findClosestTarget(int i, int curr,
int B[], int M,
int K)
{
// If absolute difference is less
// then minimum value
if (abs(curr - K) < mini) {
// Update the minimum value
mini = abs(curr - K);
// Update the value of ans
ans = curr;
}
// If absolute difference between
// curr and K is equal to minimum
if (abs(curr - K) == mini) {
// Update the value of ans
ans = min(ans, curr);
}
// If i is greater than M - 1
if (i >= M)
return;
// Includes the element B[i] once
findClosestTarget(i + 1, curr + B[i],
B, M, K);
// Includes the element B[i] twice
findClosestTarget(i + 1, curr + 2 * B[i],
B, M, K);
// Excludes the element B[i]
findClosestTarget(i + 1, curr, B, M, K);
}
// Function to find a subset sum
// whose sum is closest to K
int findClosest(int A[], int B[],
int N, int M, int K)
{
// Traverse the array A[]
for (int i = 0; i < N; i++) {
// Function Call
findClosestTarget(0, A[i], B,
M, K);
}
// Return the ans
return ans;
}
// Driver Code
int main()
{
// Input
int A[] = { 2, 3 };
int B[] = { 4, 5, 30 };
int N = sizeof(A) / sizeof(A[0]);
int M = sizeof(B) / sizeof(B[0]);
int K = 18;
// Function Call
cout << findClosest(A, B, N, M, K);
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Stores the sum closest to K
static int ans = Integer.MAX_VALUE;
// Stores the minimum absolute difference
static int mini = Integer.MAX_VALUE;
// Function to choose the elements
// from the array B[]
static void findClosestTarget(int i, int curr, int B[],
int M, int K)
{
// If absolute difference is less
// then minimum value
if (Math.abs(curr - K) < mini) {
// Update the minimum value
mini = Math.abs(curr - K);
// Update the value of ans
ans = curr;
}
// If absolute difference between
// curr and K is equal to minimum
if (Math.abs(curr - K) == mini) {
// Update the value of ans
ans = Math.min(ans, curr);
}
// If i is greater than M - 1
if (i >= M)
return;
// Includes the element B[i] once
findClosestTarget(i + 1, curr + B[i], B, M, K);
// Includes the element B[i] twice
findClosestTarget(i + 1, curr + 2 * B[i], B, M, K);
// Excludes the element B[i]
findClosestTarget(i + 1, curr, B, M, K);
}
// Function to find a subset sum
// whose sum is closest to K
static int findClosest(int A[], int B[], int N, int M,
int K)
{
// Traverse the array A[]
for (int i = 0; i < N; i++) {
// Function Call
findClosestTarget(0, A[i], B, M, K);
}
// Return the ans
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Input
int A[] = { 2, 3 };
int B[] = { 4, 5, 30 };
int N = A.length;
int M = B.length;
int K = 18;
// Function Call
System.out.print(findClosest(A, B, N, M, K));
}
}
// This code is contributed by Kingash.
Python3
# Python3 program of the above approach # Stores the sum closest to K ans = 10**8 # Stores the minimum absolute difference mini = 10**8 # Function to choose the elements # from the array B[] def findClosestTarget(i, curr, B, M, K): global ans, mini # If absolute difference is less # then minimum value if (abs(curr - K) < mini): # Update the minimum value mini = abs(curr - K) # Update the value of ans ans = curr # If absolute difference between # curr and K is equal to minimum if (abs(curr - K) == mini): # Update the value of ans ans = min(ans, curr) # If i is greater than M - 1 if (i >= M): return # Includes the element B[i] once findClosestTarget(i + 1, curr + B[i], B, M, K) # Includes the element B[i] twice findClosestTarget(i + 1, curr + 2 * B[i], B, M, K) # Excludes the element B[i] findClosestTarget(i + 1, curr, B, M, K) # Function to find a subset sum # whose sum is closest to K def findClosest(A, B, N, M, K): # Traverse the array A[] for i in range(N): # Function Call findClosestTarget(0, A[i], B, M, K) # Return the ans return ans # Driver Code if __name__ == '__main__': # Input A = [2, 3] B = [4, 5, 30] N = len(A) M = len(B) K = 18 # Function Call print (findClosest(A, B, N, M, K)) # This code is contributed by mohit kumar 29.
C#
// C# program of the above approach
using System;
class GFG
{
// Stores the sum closest to K
static int ans = Int32.MaxValue;
// Stores the minimum absolute difference
static int mini = Int32.MaxValue;
// Function to choose the elements
// from the array B[]
static void findClosestTarget(int i, int curr, int[] B,
int M, int K)
{
// If absolute difference is less
// then minimum value
if (Math.Abs(curr - K) < mini) {
// Update the minimum value
mini = Math.Abs(curr - K);
// Update the value of ans
ans = curr;
}
// If absolute difference between
// curr and K is equal to minimum
if (Math.Abs(curr - K) == mini) {
// Update the value of ans
ans = Math.Min(ans, curr);
}
// If i is greater than M - 1
if (i >= M)
return;
// Includes the element B[i] once
findClosestTarget(i + 1, curr + B[i], B, M, K);
// Includes the element B[i] twice
findClosestTarget(i + 1, curr + 2 * B[i], B, M, K);
// Excludes the element B[i]
findClosestTarget(i + 1, curr, B, M, K);
}
// Function to find a subset sum
// whose sum is closest to K
static int findClosest(int[] A, int[] B, int N, int M,
int K)
{
// Traverse the array A[]
for (int i = 0; i < N; i++) {
// Function Call
findClosestTarget(0, A[i], B, M, K);
}
// Return the ans
return ans;
}
// Driver Code
public static void Main()
{
// Input
int[] A = { 2, 3 };
int[] B = { 4, 5, 30 };
int N = A.Length;
int M = B.Length;
int K = 18;
// Function Call
Console.WriteLine(findClosest(A, B, N, M, K));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Stores the sum closest to K
let ans = Number.MAX_SAFE_INTEGER
// Stores the minimum absolute difference
let mini = Number.MAX_SAFE_INTEGER
// Function to choose the elements
// from the array B[]
function findClosestTarget(i, curr, B,
M, K) {
// If absolute difference is less
// then minimum value
if (Math.abs(curr - K) < mini) {
// Update the minimum value
mini = Math.abs(curr - K);
// Update the value of ans
ans = curr;
}
// If absolute difference between
// curr and K is equal to minimum
if (Math.abs(curr - K) == mini) {
// Update the value of ans
ans = Math.min(ans, curr);
}
// If i is greater than M - 1
if (i >= M)
return;
// Includes the element B[i] once
findClosestTarget(i + 1, curr + B[i], B, M, K);
// Includes the element B[i] twice
findClosestTarget(i + 1, curr + 2 * B[i], B, M, K);
// Excludes the element B[i]
findClosestTarget(i + 1, curr, B, M, K);
}
// Function to find a subset sum
// whose sum is closest to K
function findClosest(A, B, N, M, K) {
// Traverse the array A[]
for (let i = 0; i < N; i++) {
// Function Call
findClosestTarget(0, A[i], B, M, K);
}
// Return the ans
return ans;
}
// Driver Code
// Input
let A = [2, 3];
let B = [4, 5, 30];
let N = A.length;
let M = B.length;
let K = 18;
// Function Call
document.write(findClosest(A, B, N, M, K));
//This code is contributed by Hritik.
</script>
Producción:
17
Complejidad de Tiempo: O(N * 3 M )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ajaykr00kj y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA