Dada una array arr[] que tiene N pares de enteros de la forma (x, y) , la tarea es maximizar los valores de la suma y en los pares seleccionados, de modo que si se selecciona un par (xi , yi ) , el siguiente x Los pares i no se pueden seleccionar.
Ejemplos:
Entrada: arr[]= {{1, 5}, {2, 7}, {1, 4}, {1, 5}, {1, 10}}
Salida: 19
Explicación: Elija el par en el índice i = 0 es decir, (1, 5). Por lo tanto, no se puede seleccionar el siguiente par. Del mismo modo, seleccione los pares en el índice 2 y 4, es decir, (1, 4) y (1, 10). Por lo tanto, la suma de todos los valores de y de los pares seleccionados es 5+4+10 = 19, que es el máximo posible.Entrada: arr[] = {{1, 5}, {2, 10}, {3, 3}, {7, 4}}
Salida: 10
Enfoque: El problema dado se puede resolver usando programación dinámica . Cree una array dp[] , donde dp[i] representa la suma máxima posible de los elementos seleccionados de la array arr[] en el rango [i, N) e inicialice el valor de todos los índices con 0 . Por lo tanto, la array dp[] se puede calcular usando la siguiente relación:
dp[i] = max( dp[i + 1], dp[i + x i + 1] + y i )
Por lo tanto, calcule el valor de cada estado en dp[i] para todos los valores de i en el rango (N, 0) . El valor almacenado en dp[0] será la respuesta requerida.
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 maximize sum of selected
// integers from an array of pair
// of integers as per given condition
int maximizeSum(vector<pair<int, int> > arr, int N)
{
// Stores the DP states
vector<int> dp(N + 1, 0);
// Initial Condition
dp[N - 1] = arr[N - 1].second;
// Loop to traverse the array
// in the range (N - 1, 0]
for (int i = N - 2; i >= 0; i--) {
// If it is in range
if (i + arr[i].first < N)
// Calculate dp[i]
dp[i] = max(dp[i + 1],
dp[i + arr[i].first + 1]
+ arr[i].second);
else
dp[i] = dp[i + 1];
}
// Return Answer
return dp[0];
}
// Driver Code
int main()
{
vector<pair<int, int> > arr = {
{ 1, 5 }, { 2, 7 }, { 1, 4 }, { 1, 5 }, { 1, 10 }
};
cout << maximizeSum(arr, arr.size());
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
// User defined Pair class
class Pair {
int first;
int second;
// Constructor
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class GFG {
// Function to maximize sum of selected
// integers from an array of pair
// of integers as per given condition
static int maximizeSum(Pair arr[ ], int N)
{
// Stores the DP states
int dp[] = new int[N + 1];
// Initial Condition
dp[N - 1] = arr[N - 1].second;
// Loop to traverse the array
// in the range (N - 1, 0]
for (int i = N - 2; i >= 0; i--) {
// If it is in range
if (i + arr[i].first < N)
// Calculate dp[i]
dp[i] = Math.max(dp[i + 1],
dp[i + arr[i].first + 1]
+ arr[i].second);
else
dp[i] = dp[i + 1];
}
// Return Answer
return dp[0];
}
// Driver Code
public static void main (String[] args)
{
int n = 5;
// Array of Pair
Pair arr[] = new Pair[n];
arr[0] = new Pair(1, 5);
arr[1] = new Pair(2, 7);
arr[2] = new Pair(1, 4);
arr[3] = new Pair(1, 5);
arr[4] = new Pair(1, 10);
System.out.print(maximizeSum(arr, n));
}
}
// This code is contributed by hrithikgarg03188.
Python3
# Python code for the above approach
# Function to maximize sum of selected
# integers from an array of pair
# of integers as per given condition
def maximizeSum(arr, N):
# Stores the DP states
dp = [0] * (N + 1)
# Initial Condition
dp[N - 1] = arr[N - 1]["second"]
# Loop to traverse the array
# in the range (N - 1, 0]
for i in range(N - 2, -1, -1):
# If it is in range
if (i + arr[i]["first"] < N):
# Calculate dp[i]
dp[i] = max(dp[i + 1],
dp[i + arr[i]["first"] + 1]
+ arr[i]["second"])
else:
dp[i] = dp[i + 1]
# Return Answer
return dp[0]
# Driver Code
arr = [{"first": 1, "second": 5},
{"first": 2, "second": 7},
{"first": 1, "second": 4},
{"first": 1, "second": 5},
{"first": 1, "second": 10}
]
print(maximizeSum(arr, len(arr)))
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
// User defined Pair class
class Pair {
public int first;
public int second;
// Constructor
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
public class GFG {
// Function to maximize sum of selected
// integers from an array of pair
// of integers as per given condition
static int maximizeSum(Pair []arr, int N)
{
// Stores the DP states
int []dp = new int[N + 1];
// Initial Condition
dp[N - 1] = arr[N - 1].second;
// Loop to traverse the array
// in the range (N - 1, 0]
for (int i = N - 2; i >= 0; i--) {
// If it is in range
if (i + arr[i].first < N)
// Calculate dp[i]
dp[i] = Math.Max(dp[i + 1],
dp[i + arr[i].first + 1]
+ arr[i].second);
else
dp[i] = dp[i + 1];
}
// Return Answer
return dp[0];
}
// Driver Code
public static void Main(String[] args)
{
int n = 5;
// Array of Pair
Pair []arr = new Pair[n];
arr[0] = new Pair(1, 5);
arr[1] = new Pair(2, 7);
arr[2] = new Pair(1, 4);
arr[3] = new Pair(1, 5);
arr[4] = new Pair(1, 10);
Console.Write(maximizeSum(arr, n));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to maximize sum of selected
// integers from an array of pair
// of integers as per given condition
function maximizeSum(arr, N)
{
// Stores the DP states
let dp = new Array(N + 1).fill(0);
// Initial Condition
dp[N - 1] = arr[N - 1].second;
// Loop to traverse the array
// in the range (N - 1, 0]
for (let i = N - 2; i >= 0; i--) {
// If it is in range
if (i + arr[i].first < N)
// Calculate dp[i]
dp[i] = Math.max(dp[i + 1],
dp[i + arr[i].first + 1]
+ arr[i].second);
else
dp[i] = dp[i + 1];
}
// Return Answer
return dp[0];
}
// Driver Code
let arr = [{ first: 1, second: 5 },
{ first: 2, second: 7 },
{ first: 1, second: 4 },
{ first: 1, second: 5 },
{ first: 1, second: 10 }
];
document.write(maximizeSum(arr, arr.length));
// This code is contributed by Potta Lokesh
</script>
19
Complejidad temporal: O(N)
Espacio auxiliar: O(N)