Dado un entero positivo N y un arreglo arr[] de tamaño M del tipo {L, R, C} tal que C es el costo de elegir un elemento en el rango [L, R] y un entero positivo K , la tarea es encontrar el costo máximo de un valor en el rango [1, N] de modo que los valores se encuentren como máximo en K rango dado arr[] .
Ejemplos:
Entrada: arr[] = {{2, 8, 800}, {6, 9, 1500}, {4, 7, 200}, {3, 5, 400}}, K = 2
Salida: 2300
Explicación:
El elemento elegido es 6 y los costos elegidos son índices 0 y 1 tales que el 6 pertenece al rango de 2 a 8 y de 6 a 9. Por lo tanto, la suma total de los costos 800 + 1500 es 2300, que es el máximo.Entrada: arr[] = {{1, 3, 400}, {5, 5, 500}, {2, 3, 300}}, K = 3
Salida: 700
Enfoque: El problema dado se puede resolver almacenando todos los costos de cada artículo i que se encuentra en el rango de intervalo L a R, y clasificando los costos elegidos en orden no creciente . Luego comparando la suma de los primeros K costos de todos los artículos. Se pueden seguir los siguientes pasos:
- Inicialice una variable, digamos totMaxSum = 0 para almacenar la suma máxima del costo.
- Inicialice una variable, digamos suma = 0 para almacenar la i -ésima suma del artículo del costo.
- Inicialice un vector , diga currCost para almacenar los costos del i -ésimo artículo.
- Iterar sobre el rango de [1, N] usando la variable i e iterar anidado sobre el rango de [0, M – 1] usando la variable j y realizar los siguientes pasos:
- Si el valor de i se encuentra en el rango [arr[i][0], arr[i][1]] , agregue el valor de arr[i][2] al vector currCost .
- Ordene el vector currCost en orden no creciente.
- Iterar sobre el vector currCost y sumar los valores de los primeros K elementos a sum .
- Actualice el valor de totMaxSum por max(totMaxSum, sum) .
- Después de completar los pasos anteriores, imprima el valor de totMaxSum como la suma máxima.
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 the total cost
// by choosing an item which lies in
// the interval L to R
void maxTotalCost(vector<vector<int> >& arr,
int M, int N, int K)
{
// Stores the total maximum sum
int totMaxSum = 0;
for (int i = 1; i <= N; ++i) {
// Stores the cost for ith item
vector<int> currCost;
for (int j = 0; j < M; ++j) {
// Check if the ith item
// belongs in the interval
if (arr[j][0] <= i
&& arr[j][1] >= i) {
// Add the jth cost
currCost.push_back(arr[j][2]);
}
}
// Sort the currCost[] in the
// non increasing order
sort(currCost.begin(),
currCost.end(),
greater<int>());
// Stores the ith item sum
int sum = 0;
// Choose at most K costs
for (int j = 0;
j < K
&& j < currCost.size();
++j) {
// Update the sum
sum += currCost[j];
}
// Update the totMaxSum
totMaxSum = max(totMaxSum, sum);
}
// Print the value of totMaxSum
cout << totMaxSum << endl;
}
// Driver Code
int main()
{
int N = 10;
vector<vector<int> > arr = { { 2, 8, 800 },
{ 6, 9, 1500 },
{ 4, 7, 200 },
{ 3, 5, 400 } };
int M = arr.size();
int K = 2;
maxTotalCost(arr, M, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to maximize the total cost
// by choosing an item which lies in
// the interval L to R
static void maxTotalCost(int[][] arr,
int M, int N, int K)
{
// Stores the total maximum sum
int totMaxSum = 0;
for (int i = 1; i <= N; ++i) {
// Stores the cost for ith item
Vector<Integer> currCost = new Vector<Integer>();
for (int j = 0; j < M; ++j) {
// Check if the ith item
// belongs in the interval
if (arr[j][0] <= i
&& arr[j][1] >= i) {
// Add the jth cost
currCost.add(arr[j][2]);
}
}
// Sort the currCost[] in the
// non increasing order
Collections.sort(currCost,Collections.reverseOrder());
// Stores the ith item sum
int sum = 0;
// Choose at most K costs
for (int j = 0;
j < K
&& j < currCost.size();
++j) {
// Update the sum
sum += currCost.get(j);
}
// Update the totMaxSum
totMaxSum = Math.max(totMaxSum, sum);
}
// Print the value of totMaxSum
System.out.print(totMaxSum +"\n");
}
// Driver Code
public static void main(String[] args)
{
int N = 10;
int[][] arr = { { 2, 8, 800 },
{ 6, 9, 1500 },
{ 4, 7, 200 },
{ 3, 5, 400 } };
int M = arr.length;
int K = 2;
maxTotalCost(arr, M, N, K);
}
}
// This code is contributed by shikhasingrajput
Python3
# python program for the above approach # Function to maximize the total cost # by choosing an item which lies in # the interval L to R def maxTotalCost(arr, M, N, K): # Stores the total maximum sum totMaxSum = 0 for i in range(1, N + 1): # Stores the cost for ith item currCost = [] for j in range(0, M): # Check if the ith item # belongs in the interval if (arr[j][0] <= i and arr[j][1] >= i): # Add the jth cost currCost.append(arr[j][2]) # Sort the currCost[] in the # non increasing order currCost.sort() # Stores the ith item sum sum = 0 # Choose at most K costs for j in range(0, K): # Update the sum if j >= len(currCost): break sum += currCost[j] # Update the totMaxSum totMaxSum = max(totMaxSum, sum) # Print the value of totMaxSum print(totMaxSum) # Driver Code if __name__ == "__main__": N = 10 arr = [[2, 8, 800], [6, 9, 1500], [4, 7, 200], [3, 5, 400] ] M = len(arr) K = 2 maxTotalCost(arr, M, N, K) # This code is contributed by rakeshsahni
C#
// C++ program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to maximize the total cost
// by choosing an item which lies in
// the interval L to R
static void maxTotalCost(int[, ] arr, int M, int N,
int K)
{
// Stores the total maximum sum
int totMaxSum = 0;
for (int i = 1; i <= N; ++i) {
// Stores the cost for ith item
List<int> currCost = new List<int>();
for (int j = 0; j < M; ++j) {
// Check if the ith item
// belongs in the interval
if (arr[j, 0] <= i && arr[j, 1] >= i) {
// Add the jth cost
currCost.Add(arr[j, 2]);
}
}
// Sort the currCost[] in the
// non increasing order
currCost.Sort();
// Stores the ith item sum
int sum = 0;
// Choose at most K costs
for (int j = 0; j < K && j < currCost.Count;
++j) {
// Update the sum
sum += currCost[j];
}
// Update the totMaxSum
totMaxSum = Math.Max(totMaxSum, sum);
}
// Print the value of totMaxSum
Console.WriteLine(totMaxSum);
}
// Driver Code
public static void Main()
{
int N = 10;
int[, ] arr = { { 2, 8, 800 },
{ 6, 9, 1500 },
{ 4, 7, 200 },
{ 3, 5, 400 } };
int M = arr.GetLength(0);
int K = 2;
maxTotalCost(arr, M, N, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to maximize the total cost
// by choosing an item which lies in
// the interval L to R
function maxTotalCost(arr,
M, N, K)
{
// Stores the total maximum sum
let totMaxSum = 0;
for (let i = 1; i <= N; ++i) {
// Stores the cost for ith item
let currCost = [];
for (let j = 0; j < M; ++j) {
// Check if the ith item
// belongs in the interval
if (arr[j][0] <= i
&& arr[j][1] >= i) {
// Add the jth cost
currCost.push(arr[j][2]);
}
}
// Sort the currCost[] in the
// non increasing order
currCost.sort(function (a, b) { return b - a })
// Stores the ith item sum
let sum = 0;
// Choose at most K costs
for (let j = 0;
j < K
&& j < currCost.length;
++j) {
// Update the sum
sum += currCost[j];
}
// Update the totMaxSum
totMaxSum = Math.max(totMaxSum, sum);
}
// Print the value of totMaxSum
document.write(totMaxSum + '<br>');
}
// Driver Code
let N = 10;
let arr = [[2, 8, 800],
[6, 9, 1500],
[4, 7, 200],
[3, 5, 400]];
let M = arr.length;
let K = 2;
maxTotalCost(arr, M, N, K);
// This code is contributed by Potta Lokesh
</script>
Producción:
2300
Complejidad de tiempo: O(N*M*log M)
Espacio auxiliar: O(N*M)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA