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