La suma máxima posible de elementos de array no adyacentes que no exceda K

Dada una array arr[] que consiste en N enteros y un entero K , la tarea es seleccionar algunos elementos de array no adyacentes con la suma máxima posible que no exceda K .

Ejemplos:

Entrada: arr[] = {50, 10, 20, 30, 40}, K = 100
Salida: 90
Explicación: Para maximizar la suma que no excede K(= 100), seleccione los elementos 50 y 40.
Por lo tanto, máximo suma posible = 90.

Entrada: arr[] = {20, 10, 17, 12, 8, 9}, K = 64
Salida: 46
Explicación: Para maximizar la suma que no excede K(= 64), seleccione los elementos 20, 17 y 9.
Por lo tanto, suma máxima posible = 46.

Enfoque ingenuo: el enfoque más simple es generar recursivamente todos los subconjuntos posibles de la array dada y, para cada subconjunto, verificar si no contiene elementos adyacentes y si la suma no excede K . Entre todos los subconjuntos para los que se cumple la condición anterior, imprima la suma máxima obtenida para cualquier subconjunto.

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
// maximum sum not exceeding
// K possible by selecting
// a subset of non-adjacent elements
int maxSum(int a[],
           int n, int k)
{
  // Base Case
  if (n <= 0)
    return 0;
 
  // Not selecting current
  // element
  int option = maxSum(a,
                      n - 1, k);
 
  // If selecting current
  // element is possible
  if (k >= a[n - 1])
    option = max(option,
                 a[n - 1] +
             maxSum(a, n - 2,
                    k - a[n - 1]));
 
  // Return answer
  return option;
}
 
// Driver Code
int main()
{
  // Given array arr[]
  int arr[] = {50, 10,
               20, 30, 40};
 
  int N = sizeof(arr) /
          sizeof(arr[0]);
 
  // Given K
  int K = 100;
 
  // Function Call
  cout << (maxSum(arr,
                  N, K));
}
 
// This code is contributed by gauravrajput1

// Java program for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to find the maximum sum
    // not exceeding K possible by selecting
    // a subset of non-adjacent elements
    public static int maxSum(
        int a[], int n, int k)
    {
        // Base Case
        if (n <= 0)
            return 0;
 
        // Not selecting current element
        int option = maxSum(a, n - 1, k);
 
        // If selecting current element
        // is possible
        if (k >= a[n - 1])
            option = Math.max(
                option,
                a[n - 1]
                    + maxSum(a, n - 2,
                             k - a[n - 1]));
 
        // Return answer
        return option;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array arr[]
        int arr[] = { 50, 10, 20, 30, 40 };
 
        int N = arr.length;
 
        // Given K
        int K = 100;
 
        // Function Call
        System.out.println(maxSum(arr, N, K));
    }
}

# Python3 program for the above approach
 
# Function to find the maximum sum
# not exceeding K possible by selecting
# a subset of non-adjacent elements
def maxSum(a, n, k):
     
    # Base Case
    if (n <= 0):
        return 0
 
    # Not selecting current element
    option = maxSum(a, n - 1, k)
 
    # If selecting current element
    # is possible
    if (k >= a[n - 1]):
        option = max(option, a[n - 1] +
        maxSum(a, n - 2, k - a[n - 1]))
 
    # Return answer
    return option
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr[]
    arr = [ 50, 10, 20, 30, 40 ]
 
    N = len(arr)
 
    # Given K
    K = 100
 
    # Function Call
    print(maxSum(arr, N, K))
 
# This code is contributed by mohit kumar 29

// C# program for the
// above approach
using System;
class GFG{
 
// Function to find the maximum
// sum not exceeding K possible
// by selecting a subset of
// non-adjacent elements
public static int maxSum(int []a,
                         int n, int k)
{
  // Base Case
  if (n <= 0)
    return 0;
 
  // Not selecting current element
  int option = maxSum(a, n - 1, k);
 
  // If selecting current
  // element is possible
  if (k >= a[n - 1])
    option = Math.Max(option, a[n - 1] +
                      maxSum(a, n - 2,
                             k - a[n - 1]));
   
  // Return answer
  return option;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  int []arr = {50, 10, 20, 30, 40};
 
  int N = arr.Length;
 
  // Given K
  int K = 100;
 
  // Function Call
  Console.WriteLine(maxSum(arr, N, K));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program for the
// above approach
 
// Function to find the maximum sum
// not exceeding K possible by selecting
// a subset of non-adjacent elements
function maxSum(a, n, k)
{
     
    // Base Case
    if (n <= 0)
        return 0;
 
    // Not selecting current element
    let option = maxSum(a, n - 1, k);
 
    // If selecting current element
    // is possible
    if (k >= a[n - 1])
        option = Math.max(option, a[n - 1] +
             maxSum(a, n - 2, k - a[n - 1]));
 
    // Return answer
    return option;
}
 
// Driver Code
 
// Given array arr[]
let arr = [ 50, 10, 20, 30, 40 ];
 
let N = arr.length;
 
// Given K
let K = 100;
 
// Function Call
document.write(maxSum(arr, N, K));
 
// This code is contributed by target_2 
 
</script>

90

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

Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar Programación Dinámica . Existen dos opciones posibles para cada elemento de la array:

1. O salte el elemento actual y continúe con el siguiente elemento.
2. Seleccione el elemento actual solo si es menor o igual a K .

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

1. Inicialice una array dp[N][K+1] con -1 donde dp[i][j] almacenará la suma máxima para hacer la suma j usando elementos hasta el índice i .
2. A partir de la transición anterior, encuentre las sumas máximas si se selecciona el elemento actual y si no se selecciona, recursivamente .
3. Almacene la respuesta mínima para el estado actual.
4. Además, agregue la condición base de que si el estado actual (i, j) ya se visitó, es decir, dp[i][j]!=-1 devuelva dp[i][j] .
5. Imprime dp[N][K] como la suma máxima posible.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Initialize dp
int dp[1005][1005];
 
// Function find the maximum sum that
// doesn't exceeds K by choosing elements
int maxSum(int* a, int n, int k)
{
     
    // Base Case
    if (n <= 0)
        return 0;
 
    // Return the memoized state
    if (dp[n][k] != -1)
        return dp[n][k];
 
    // Dont pick the current element
    int option = maxSum(a, n - 1, k);
 
    // Pick the current element
    if (k >= a[n - 1])
        option = max(option,
                     a[n - 1] +
             maxSum(a, n - 2,
                 k - a[n - 1]));
 
    // Return and store the result
    return dp[n][k] = option;
}
 
// Driver Code
int main()
{
    int N = 5;
 
    int arr[] = { 50, 10, 20, 30, 40 };
 
    int K = 100;
 
    // Fill dp array with -1
    memset(dp, -1, sizeof(dp));
 
    // Print answer
    cout << maxSum(arr, N, K) << endl;
}
 
// This code is contributed by bolliranadheer

// Java program for the above approach
 
import java.util.*;
 
class GFG {
 
    // Function find the maximum sum that
    // doesn't exceeds K by choosing elements
    public static int maxSum(int a[], int n,
                             int k, int[][] dp)
    {
        // Base Case
        if (n <= 0)
            return 0;
 
        // Return the memoized state
        if (dp[n][k] != -1)
            return dp[n][k];
 
        // Dont pick the current element
        int option = maxSum(a, n - 1,
                            k, dp);
 
        // Pick the current element
        if (k >= a[n - 1])
            option = Math.max(
                option,
                a[n - 1]
                    + maxSum(a, n - 2,
                             k - a[n - 1],
                             dp));
 
        // Return and store the result
        return dp[n][k] = option;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 50, 10, 20, 30, 40 };
 
        int N = arr.length;
 
        int K = 100;
 
        // Initialize dp
        int dp[][] = new int[N + 1][K + 1];
 
        for (int i[] : dp) {
            Arrays.fill(i, -1);
        }
        // Print answer
        System.out.println(maxSum(arr, N, K, dp));
    }
}

# Python3 program for the
# above approach
 
# Function find the maximum
# sum that doesn't exceeds K
# by choosing elements
def maxSum(a, n, k, dp):
   
    # Base Case
    if (n <= 0):
        return 0;
 
    # Return the memoized state
    if (dp[n][k] != -1):
        return dp[n][k];
 
    # Dont pick the current
    # element
    option = maxSum(a, n - 1,
                    k, dp);
 
    # Pick the current element
    if (k >= a[n - 1]):
        option = max(option, a[n - 1] +
                 maxSum(a, n - 2,
                        k - a[n - 1], dp));
    dp[n][k] = option;
     
    # Return and store
    # the result
    return dp[n][k];
 
# Driver Code
if __name__ == '__main__':
   
    arr = [50, 10, 20,
           30, 40];
    N = len(arr);
    K = 100;
    # Initialize dp
    dp = [[-1 for i in range(K + 1)]
              for j in range(N + 1)]
 
    # Print answer
    print(maxSum(arr, N,
                 K, dp));
 
# This code is contributed by shikhasingrajput

// C# program for the
// above approach
using System;
class GFG{
 
// Function find the maximum
// sum that doesn't exceeds K
// by choosing elements
public static int maxSum(int []a, int n,
                         int k, int[,] dp)
{
  // Base Case
  if (n <= 0)
    return 0;
 
  // Return the memoized
  // state
  if (dp[n, k] != -1)
    return dp[n, k];
 
  // Dont pick the current
  // element
  int option = maxSum(a, n - 1,
                      k, dp);
 
  // Pick the current element
  if (k >= a[n - 1])
    option = Math.Max(option, a[n - 1] +
                      maxSum(a, n - 2,
                             k - a[n - 1],
                             dp));
 
  // Return and store the
  // result
  return dp[n, k] = option;
}
 
// Driver Code
public static void Main(String[] args)
{
  int []arr = {50, 10, 20, 30, 40};
  int N = arr.Length;
  int K = 100;
   
  // Initialize dp
  int [,]dp = new int[N + 1,
                      K + 1];
 
  for (int j = 0; j < N + 1; j++)
  {
    for (int k = 0; k < K + 1; k++)
      dp[j, k] = -1;
  }
   
  // Print answer
  Console.WriteLine(maxSum(arr, N,
                           K, dp));
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Javascript program to implement
// the above approach
 
    // Function find the maximum sum that
    // doesn't exceeds K by choosing elements
    function maxSum(a, n, k, dp)
    {
        // Base Case
        if (n <= 0)
            return 0;
 
        // Return the memoized state
        if (dp[n][k] != -1)
            return dp[n][k];
 
        // Dont pick the current element
        let option = maxSum(a, n - 1,
                            k, dp);
 
        // Pick the current element
        if (k >= a[n - 1])
            option = Math.max(
                option,
                a[n - 1]
                    + maxSum(a, n - 2,
                             k - a[n - 1],
                             dp));
 
        // Return and store the result
        return dp[n][k] = option;
    }
 
// Driver Code
 
 // Given array
  let arr = [ 50, 10, 20, 30, 40 ];
 
        let N = arr.length;
 
        let K = 100;
 
        // Initialize dp
        let dp = new Array(N + 1);
        // Loop to create 2D array using 1D array
        for (var i = 0; i < 1000; i++) {
            dp[i] = new Array(2);
        }
 
       for (var i = 0; i < 1000; i++) {
            for (var j = 0; j < 1000; j++) {
            dp[i][j] = -1;
        }
        }
        // Print answer
        document.write(maxSum(arr, N, K, dp));
          
</script>

90

Complejidad de tiempo: O(N*K), donde N es el tamaño de la array dada y K es el límite.
Espacio Auxiliar: O(N)