Maximizar la suma de las ganancias de N artículos de modo que la ganancia del i-ésimo artículo sea el producto de su peso y el recuento de distintos valores elegidos

Dada una array arr[] que consta de N pares de elementos como {valor, peso} , la tarea es encontrar la suma máxima de ganancias al elegir todos los N elementos dados, de modo que la ganancia por elegir el i ^-ésimo elemento se calcule como el producto de su peso y número de valores distintos ya tomados.

Ejemplos:

Entrada: arr[] = {(1, 4), (2, 3), (1, 2), (3, 2)}
Salida: 27
Explicación:
A continuación se muestra el orden de elección de artículos para maximizar la ganancia:

• Elija el segundo elemento, es decir, arr[2] = (1, 2). La ganancia del artículo elegido actualmente es 2 * 1 = 2.
• Elija el tercer elemento, es decir, arr[3] = (3, 2). La ganancia del artículo elegido actualmente es 2 * 2 = 4.
• Elija el primer elemento, es decir, arr[1] = (2, 3). La ganancia del artículo elegido actualmente es 3 * 3 = 9.
• Elija el elemento 0, es decir, arr[0] = (1, 4). La ganancia del artículo elegido actualmente es 4 * 3 = 12.

Por lo tanto, el beneficio total es 2 + 4 + 9 + 12 = 27, que es el máximo entre todas las combinaciones posibles de N pares elegidos.

Entrada: arr[] = {(2, 2), (1, 2), (3, 2)}
Salida: 12

Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . La idea es ordenar la array dada arr[] con respecto al peso de los elementos y todos los elementos distintos se eligen primero y luego los elementos restantes. Siga los pasos a continuación para resolver el problema dado:

• Inicialice un conjunto , digamos elementos , para almacenar todos los elementos únicos.
• Inicialice una variable, digamos uniqCnt = 0 , para almacenar el recuento de elementos únicos.
• Inicialice una variable, digamos maxProfit = 0 , para almacenar la ganancia máxima total.
• Inicialice una variable, digamos totWeight = 0 , para almacenar el peso total de los elementos que no son únicos.
• Recorra la array arr[] y almacene todos los elementos únicos en los elementos establecidos .
• Ordene la array arr[] en orden ascendente de sus pesos.
• Almacene el recuento de elementos únicos como uniqCnt = items.size() y elimine todos los elementos de los elementos.
• Recorra la array dada arr[] y verifique la siguiente condición:
  • if(!items.count(arr[i].first)) si esto es cierto, entonces inserte el elemento arr[i].first en los elementos establecidos y calcule la ganancia y actualícela a maxProfit por maxProfit += items.size() * arr[i].segundo .
  • De lo contrario, actualice totWeight como totWeight += arr[i].second .
• Calcule la ganancia de los artículos que no son únicos y actualice maxProfit como maxProfit += totWeight * uniqCnt .
• Después de completar los pasos anteriores, imprima el valor de maxProfit como la ganancia máxima resultante.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Comparator function to sort vector
// with respect to the second value
bool comp(pair<int, int> a, pair<int, int> b)
{
    if (a.second > b.second)
        return false;
 
    return true;
}
 
// Function to maximize the total profit
// by choosing  the array of items in a
// particular order
int maxProfit(vector<pair<int, int> >& arr,
              int N)
{
 
    // Stores the unique items
    set<int> items;
 
    for (int i = 0; i < N; i++) {
 
        // Store all the unique items
        items.insert(arr[i].first);
    }
 
    // Sort the arr with respect to
    // the weights
    sort(arr.begin(), arr.end(), comp);
 
    // Stores the number of unique
    // items count
    int uniqCnt = items.size();
 
    // Clear the set items
    items.clear();
 
    // Stores the maximum profit
    int maxProfit = 0;
 
    // Stores the total weight of items
    // which are not unique
    int totWeight = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Check the current item is unique
        if (!items.count(arr[i].first)) {
 
            // Insert the current item
            // into the items set
            items.insert(arr[i].first);
 
            // Calculate the profit for
            // the current item and
            // update the maxProfit
            maxProfit += items.size() * arr[i].second;
        }
        else
            // Update the totWeight by
            // adding current item weight
            totWeight += arr[i].second;
    }
 
    // Update the maxProfit by calculating
    // the profit for items which are not
    // unique and adding it to maxProfit
    maxProfit += totWeight * uniqCnt;
 
    // Return maxProfit
    return maxProfit;
}
 
// Driver Code
int main()
{
    vector<pair<int, int> > arr{
        { 1, 4 }, { 2, 3 }, { 1, 2 }, { 3, 2 }
    };
    int N = arr.size();
    cout << maxProfit(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
    static class pair
    {
        int first, second;
        public pair(int first, int second) 
        {
            this.first = first;
            this.second = second;
        }   
    }
// Comparator function to sort vector
// with respect to the second value
boolean comp(pair a, pair b)
{
    if (a.second > b.second)
        return false;
 
    return true;
}
 
// Function to maximize the total profit
// by choosing  the array of items in a
// particular order
static int maxProfit(pair[] arr,
              int N)
{
 
    // Stores the unique items
    HashSet<Integer> items = new HashSet<Integer>();
 
    for (int i = 0; i < N; i++) {
 
        // Store all the unique items
        items.add(arr[i].first);
    }
 
    // Sort the arr with respect to
    // the weights
    Arrays.sort(arr,(a,b)->a.second-b.second);
 
    // Stores the number of unique
    // items count
    int uniqCnt = items.size();
 
    // Clear the set items
    items.clear();
 
    // Stores the maximum profit
    int maxProfit = 0;
 
    // Stores the total weight of items
    // which are not unique
    int totWeight = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Check the current item is unique
        if (!items.contains(arr[i].first)) {
 
            // Insert the current item
            // into the items set
            items.add(arr[i].first);
 
            // Calculate the profit for
            // the current item and
            // update the maxProfit
            maxProfit += items.size() * arr[i].second;
        }
        else
            // Update the totWeight by
            // adding current item weight
            totWeight += arr[i].second;
    }
 
    // Update the maxProfit by calculating
    // the profit for items which are not
    // unique and adding it to maxProfit
    maxProfit += totWeight * uniqCnt;
 
    // Return maxProfit
    return maxProfit;
}
 
// Driver Code
public static void main(String[] args)
{
    pair[] arr = {
            new pair( 1, 4 ), new pair( 2, 3 ), new pair( 1, 2 ), new pair( 3, 2 )
    };
    int N = arr.length;
    System.out.print(maxProfit(arr, N));
 
}
}
 
// This code is contributed by 29AjayKumar

# Python Program to implement
# the above approach
 
# Function to maximize the total profit
# by choosing  the array of items in a
# particular order
def maxProfit(arr, N):
 
    # Stores the unique items
    items = set()
 
    for i in range(N):
 
        # Store all the unique items
        items.add(arr[i]["first"])
 
    # Sort the arr with respect to
    # the weights
 
    arr = sorted(arr, key=lambda i: i['second'])
 
    # Stores the number of unique
    # items count
    uniqCnt = len(items)
 
    # Clear the set items
    items.clear()
 
    # Stores the maximum profit
    maxProfit = 0
 
    # Stores the total weight of items
    # which are not unique
    totWeight = 0
 
    for i in range(0, N):
 
        # Check the current item is unique
        if (not (arr[i]['first']) in items):
 
            # Insert the current item
            # into the items set
            items.add(arr[i]['first'])
 
            # Calculate the profit for
            # the current item and
            # update the maxProfit
            maxProfit += len(items) * arr[i]['second']
 
        else:
            # Update the totWeight by
            # adding current item weight
            totWeight += arr[i]['second']
 
    # Update the maxProfit by calculating
    # the profit for items which are not
    # unique and adding it to maxProfit
    maxProfit += totWeight * uniqCnt
 
    # Return maxProfit
    return maxProfit
 
 
# Driver Code
arr = [
    {"first": 1, "second": 4},
    {"first": 2, "second": 3},
    {"first": 1, "second": 2},
    {"first": 3, "second": 2}
]
N = len(arr)
print(maxProfit(arr, N))
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
    public class pair : IComparable<pair>
    {
        public int first,second;
        public pair(int first, int second)
        {
            this.first = first;
            this.second = second; 
        }
 
        // Comparator function to sort vector
        // with respect to the second value
        public int CompareTo(pair p)
        {
            return this.second - p.second;
        }
    }
 
// Function to maximize the total profit
// by choosing  the array of items in a
// particular order
static int maxProfit(pair[] arr,
              int N)
{
 
    // Stores the unique items
    HashSet<int> items = new HashSet<int>();
 
    for (int i = 0; i < N; i++) {
 
        // Store all the unique items
        items.Add(arr[i].first);
    }   
 
    // Sort the arr with respect to
    // the weights
    Array.Sort(arr);
 
    // Stores the number of unique
    // items count
    int uniqCnt = items.Count;
 
    // Clear the set items
    items.Clear();
 
    // Stores the maximum profit
    int maxProfit = 0;
 
    // Stores the total weight of items
    // which are not unique
    int totWeight = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Check the current item is unique
        if (!items.Contains(arr[i].first)) {
 
            // Insert the current item
            // into the items set
            items.Add(arr[i].first);
 
            // Calculate the profit for
            // the current item and
            // update the maxProfit
            maxProfit += items.Count * arr[i].second;
        }
        else
            // Update the totWeight by
            // adding current item weight
            totWeight += arr[i].second;
    }
 
    // Update the maxProfit by calculating
    // the profit for items which are not
    // unique and adding it to maxProfit
    maxProfit += totWeight * uniqCnt;
 
    // Return maxProfit
    return maxProfit;
}
 
// Driver Code
public static void Main(String[] args)
{
    pair[] arr = {
            new pair( 1, 4 ), new pair( 2, 3 ), new pair( 1, 2 ), new pair( 3, 2 )
    };
    int N = arr.Length;
    Console.Write(maxProfit(arr, N));
 
}
}
 
// This code is contributed by shikhasingrajput

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to maximize the total profit
        // by choosing  the array of items in a
        // particular order
        function maxProfit(arr,
            N) {
 
            // Stores the unique items
            let items = new Set();
 
            for (let i = 0; i < N; i++) {
 
                // Store all the unique items
                items.add(arr[i].first);
            }
 
            // Sort the arr with respect to
            // the weights
            arr.sort(function (a, b) { return a.second - b.second })
            // Stores the number of unique
            // items count
            let uniqCnt = items.size;
 
            // Clear the set items
            items.clear();
 
            // Stores the maximum profit
            let maxProfit = 0;
 
            // Stores the total weight of items
            // which are not unique
            let totWeight = 0;
 
            for (let i = 0; i < N; i++) {
 
                // Check the current item is unique
                if (!items.has(arr[i].first)) {
 
                    // Insert the current item
                    // into the items set
                    items.add(arr[i].first);
 
                    // Calculate the profit for
                    // the current item and
                    // update the maxProfit
                    maxProfit += items.size * arr[i].second;
                }
                else
                    // Update the totWeight by
                    // adding current item weight
                    totWeight += arr[i].second;
            }
 
            // Update the maxProfit by calculating
            // the profit for items which are not
            // unique and adding it to maxProfit
            maxProfit += totWeight * uniqCnt;
 
            // Return maxProfit
            return maxProfit;
        }
 
        // Driver Code
        let arr = [
            { "first": 1, "second": 4 },
            { "first": 2, "second": 3 },
            { "first": 1, "second": 2 },
            { "first": 3, "second": 2 }
        ]
        let N = arr.length;
        document.write(maxProfit(arr, N));
 
     // This code is contributed by Potta Lokesh
 
    </script>

27

Complejidad de tiempo : O (N * logN), ya que estamos usando una función de clasificación.

Espacio auxiliar : O(N), ya que estamos usando espacio extra.