Suma máxima de elementos divisibles por K de la array dada

Dada una array de enteros y un número K. La tarea es encontrar la suma máxima que es divisible por K de la array dada.
Ejemplos: 
 

Entrada: arr[] = {3, 6, 5, 1, 8}, k = 3 
Salida: 18 
Explicación: 18 está formado por los elementos 3, 6, 1, 8.
Entrada: arr = { 43, 1, 17 , 26, 15 } , k = 16 
Salida: 32 
Explicación: 32 está formado por los elementos 17, 15. 
 

Enfoque ingenuo: verifica recursivamente todas las combinaciones posibles para encontrar la solución. La solución es de complejidad temporal exponencial y por lo tanto ineficiente.
Enfoque eficiente: un enfoque de programación dinámica mediante el mantenimiento de una array 2-D dp que almacena el estado de la variable sum e i (donde sum es la suma actual e i es el i-ésimo índice de la array de enteros). Al repetir sobre todos los elementos, calcule la suma incluyendo el elemento en el índice i y excluyéndolo y verifique si es divisible por k. Si es así, almacene el máximo de ellos en dp[i][sum] y regrese.
El siguiente código es la implementación del enfoque anterior: 
 

C++

#include <bits/stdc++.h>
using namespace std;
 
int dp[1001][1001];
 
// Function to return the maximum sum
// divisible by k from elements of v
int find_max(int i, int sum, vector<int>& v,int k)
{
 
    if (i == v.size())
        return 0;
 
    if (dp[i][sum] != -1)
        return dp[i][sum];
 
    int ans = 0;
    // check if sum of elements excluding the
    // current one is divisible by k
    if ((sum + find_max(i + 1, sum, v, k)) % k == 0)
        ans = find_max(i + 1, sum, v, k);
     
    // check if sum of elements including the
    // current one is divisible by k
    if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k,
                                   v, k)) % k == 0)
        // Store the maximum
        ans = max(ans, v[i] + find_max(i + 1,
                            (sum + v[i]) % k,v, k));
     
 
    return dp[i][sum] = ans;
}
 
// Driver code
int main()
{
    vector<int> arr = { 43, 1, 17, 26, 15 };
    int k = 16;
    memset(dp, -1, sizeof(dp));
    cout << find_max(0, 0, arr, k);
}

Java

class GFG{
  
static int [][]dp = new int[1001][1001];
  
// Function to return the maximum sum
// divisible by k from elements of v
static int find_max(int i, int sum, int []v, int k)
{
  
    if (i == v.length)
        return 0;
  
    if (dp[i][sum] != -1)
        return dp[i][sum];
  
    int ans = 0;
 
    // check if sum of elements excluding the
    // current one is divisible by k
    if ((sum + find_max(i + 1, sum, v, k)) % k == 0)
        ans = find_max(i + 1, sum, v, k);
      
    // check if sum of elements including the
    // current one is divisible by k
    if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k,
                                   v, k)) % k == 0)
        // Store the maximum
        ans = Math.max(ans, v[i] + find_max(i + 1,
                            (sum + v[i]) % k, v, k));
      
    return dp[i][sum] = ans;
}
  
// Driver code
public static void main(String[] args)
{
    int []arr = { 43, 1, 17, 26, 15 };
    int k = 16;
    for (int i = 0; i < 1001; i++)
        for (int j = 0; j < 1001; j++)
            dp[i][j] = -1;
    System.out.print(find_max(0, 0, arr, k));
}
}
 
// This code is contributed by 29AjayKumar

Python 3

# Python3 implementation
dp = [[-1 for i in range(1001)] for j in range(1001)]
 
# Function to return the maximum sum
# divisible by k from elements of v
def find_max(i, sum, v, k):
    if (i == len(v)):
        return 0
 
    if (dp[i][sum] != -1):
        return dp[i][sum]
 
    ans = 0
     
    # check if sum of elements excluding the
    # current one is divisible by k
    if ((sum + find_max(i + 1, sum, v, k)) % k == 0):
        ans = find_max(i + 1, sum, v, k)
     
    # check if sum of elements including the
    # current one is divisible by k
    if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k, v, k)) % k == 0):
         
        # Store the maximum
        ans = max(ans, v[i] + find_max(i + 1,(sum + v[i]) % k, v, k))
     
    dp[i][sum] = ans
 
    return dp[i][sum]
 
# Driver code
if __name__ == '__main__':
    arr = [43, 1, 17, 26, 15]
    k = 16
    print(find_max(0, 0, arr, k))
 
# This code is contributed by Surendra_Gangwar

C#

using System;
 
class GFG{
   
static int [,]dp = new int[1001,1001];
   
// Function to return the maximum sum
// divisible by k from elements of v
static int find_max(int i, int sum, int []v, int k)
{
   
    if (i == v.Length)
        return 0;
   
    if (dp[i,sum] != -1)
        return dp[i,sum];
   
    int ans = 0;
  
    // check if sum of elements excluding the
    // current one is divisible by k
    if ((sum + find_max(i + 1, sum, v, k)) % k == 0)
        ans = find_max(i + 1, sum, v, k);
       
    // check if sum of elements including the
    // current one is divisible by k
    if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k,
                                   v, k)) % k == 0)
        // Store the maximum
        ans = Math.Max(ans, v[i] + find_max(i + 1,
                            (sum + v[i]) % k, v, k));
       
    return dp[i, sum] = ans;
}
   
// Driver code
public static void Main(String[] args)
{
    int []arr = { 43, 1, 17, 26, 15 };
    int k = 16;
    for (int i = 0; i < 1001; i++)
        for (int j = 0; j < 1001; j++)
            dp[i,j] = -1;
    Console.Write(find_max(0, 0, arr, k));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to implement
// the above approach
let dp = new Array(1000 + 1);
 
// Function to return the maximum sum
// divisible by k from elements of v
function find_max(i, sum, v, k)
{
     
    if (i == v.length)
        return 0;
 
    if (dp[i][sum] != -1)
        return dp[i][sum];
 
    let ans = 0;
    // check if sum of elements excluding the
    // current one is divisible by k
    if ((sum + find_max(i + 1, sum, v, k)) % k == 0)
        ans = find_max(i + 1, sum, v, k);
     
    // check if sum of elements including the
    // current one is divisible by k
    if((sum + v[i] + find_max(i + 1,(sum + v[i]) % k,
                                   v, k)) % k == 0)
        // Store the maximum
        ans = Math.max(ans, v[i] + find_max(i + 1,
                            (sum + v[i]) % k,v, k));
                                             
    return dp[i][sum] = ans;
}
  
// Driver Code
    let arr = [ 43, 1, 17, 26, 15 ];
    let k = 16;
 
    // Loop to create 2D array using 1D array
    for (var i = 0; i < dp.length; i++) {
        dp[i] = new Array(2);
    }
 
    for (var i = 0; i < dp.length; i++) {
        for (var j = 0; j < dp.length; j++) {
 
            dp[i][j] = -1;
        }
    }
 
    document.write(find_max(0, 0, arr, k));
 
    // This code is contributed by Dharanendra L V.
</script>
Producción

32

Implementación iterativa utilizando dp de arriba hacia abajo:

Usaremos el índice y el valor del módulo de la suma como nuestros estados de dp. dp[i][j] almacenaría la suma máxima de la array hasta el i-ésimo índice cuyo módulo es j.

C++

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int k=16;
    vector<int>arr={ 43, 1, 17, 26, 15 } ;
    int n=arr.size();
    vector<vector<int>> dp(n+2, vector<int>(k, 0));
    for (int i = 1; i <= n; i++) {
         
        for (int j = 0; j < k ; j++) {
            dp[i][j] = dp[i - 1][j];
        }
         
        dp[i][arr[i - 1] % k] = max(dp[i][arr[i - 1] % k], arr[i - 1]);
       
        for (int j = 0; j < k; j++) {
            int m = (j + arr[i - 1]) % k;
            if (dp[i - 1][j] != 0)
                dp[i][m] = max(dp[i][m],arr[i - 1] + dp[i - 1][j]);
        }
       
    }
    cout <<dp[n][0];
    return 0;
}

Java

import java.util.*;
 
class GFG {
 
    public static void main(String[] args)
    {
        int k = 16;
        int[] arr = { 43, 1, 17, 26, 15 };
        int n = arr.length;
        int[][] dp = new int[n + 2][k];
        for (int i = 1; i <= n; i++) {
 
            for (int j = 0; j < k; j++) {
                dp[i][j] = dp[i - 1][j];
            }
 
            dp[i][arr[i - 1] % k] = Math.max(
                dp[i][arr[i - 1] % k], arr[i - 1]);
 
            for (int j = 0; j < k; j++) {
                int m = (j + arr[i - 1]) % k;
                if (dp[i - 1][j] != 0)
                    dp[i][m] = Math.max(dp[i][m],
                                        arr[i - 1]
                                            + dp[i - 1][j]);
            }
        }
        System.out.print(dp[n][0]);
    }
}
 
// This code is contributed by ukasp.

Python3

k = 16
arr = [ 43, 1, 17, 26, 15 ]
n = len(arr)
dp = [[0 for i in range(k)] for j in range(n+2)]
for i in range(1, n+1):
    for j in range(k):
        dp[i][j] = dp[i - 1][j]
      
    dp[i][arr[i - 1] % k] = max(dp[i][arr[i - 1] % k], arr[i - 1])
    
    for j in range(k):
        m = (j + arr[i - 1]) % k
        if dp[i - 1][j] != 0:
            dp[i][m] = max(dp[i][m],arr[i - 1] + dp[i - 1][j])
             
print(dp[n][0])
 
# This code is contributed by suresh07.

C#

using System;
class GFG {
  static void Main() {
    int k = 16;
    int[] arr = { 43, 1, 17, 26, 15 };
    int n = arr.Length;
    int[,] dp = new int[n + 2, k];
    for (int i = 1; i <= n; i++) {
          
        for (int j = 0; j < k ; j++) {
            dp[i,j] = dp[i - 1,j];
        }
          
        dp[i,arr[i - 1] % k] = Math.Max(dp[i,arr[i - 1] % k], arr[i - 1]);
        
        for (int j = 0; j < k; j++) {
            int m = (j + arr[i - 1]) % k;
            if (dp[i - 1,j] != 0)
                dp[i,m] = Math.Max(dp[i,m],arr[i - 1] + dp[i - 1,j]);
        }
    }
    Console.Write(dp[n,0]);
  }
}
 
// This code is contributed by divyesh072019.

Javascript

<script>
    let k = 16;
    let arr = [ 43, 1, 17, 26, 15 ] ;
    let n = arr.length;
    let dp = new Array(n+2);
    for(let i = 0; i < n+2; i++)
    {
        dp[i] = new Array(k);
        for(let j = 0; j < k; j++)
        {
            dp[i][j] = 0;
        }
    }
    for (let i = 1; i <= n; i++) {
          
        for (let j = 0; j < k ; j++) {
            dp[i][j] = dp[i - 1][j];
        }
          
        dp[i][arr[i - 1] % k] = Math.max(dp[i][arr[i - 1] % k], arr[i - 1]);
        
        for (let j = 0; j < k; j++) {
            let m = (j + arr[i - 1]) % k;
            if (dp[i - 1][j] != 0)
                dp[i][m] = Math.max(dp[i][m],arr[i - 1] + dp[i - 1][j]);
        }
        
    }
    document.write(dp[n][0]);
     
    // This code is contributed by mukesh07.
</script>
Producción

32

Publicación traducida automáticamente

Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *