Encuentra un subconjunto con la suma máxima bajo una condición dada

Dados los valores [] y las etiquetas [] de n elementos y un límite de entero positivo , debemos elegir un subconjunto de estos elementos de tal manera que el número del mismo tipo de etiqueta en el subconjunto sea <= límite y suma de los valores son máximos entre todas las opciones de subconjuntos posibles.

Ejemplos:  

Input: values[] = [5, 3, 7, 1, 2],
       labels[] = [5, 7, 7, 7, 6],
       limit = 2
Output: 17
Explanation:
You can select first, second, third 
and Fifth values.
So, there is 1 value of the label 5 -> {5},
    2 value of the label 7 -> {3, 7} ,
    1 value of the label 6 -> {2}.
Final subset = {5, 3, 7, 2}
Sum  = 5 + 3 + 7 + 2 = 17.

Input: values[] = [9, 8, 7, 6, 5],
       labels[] = [5, 7, 7, 7, 6],
       limit = 2
Output: 29

Enfoque: La idea es usar un Multimap y Hashmap para resolver este problema. 

• Guardaremos todos los valores y las etiquetas respectivas como un par en el Multimapa.
• En Multimap, los pares {valores, etiquetas} se ordenan en orden creciente. Por lo tanto, recorreremos el mapa múltiple al revés para obtener los pares en orden decreciente.
• Ahora, agregaremos los valores en nuestra respuesta y almacenaremos la ocurrencia de cada etiqueta en Hashmap para verificar si la cantidad de ocurrencias es <= límite.

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

// C++ program to Find subset with
// maximum sum under given condition.
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum
// sum of the subset
int MaxSumSubset(vector<int>& values,
                 vector<int>& labels,
                 int n, int limit)
{
    int res = 0;
    multimap<int, int> s;
    unordered_map<int, int> map;
 
    if (n == 0)
    {
        return 0;
    }
 
    // Pushing the pair into
    // the multimap
    for (int i = 0; i < n; i++)
    {
        s.insert({ values[i],
                  labels[i] });
    }
 
    // Traversing the multimap
    // in reverse
    for (auto it = s.rbegin();
         it != s.rend() && n > 0; it++)
    {
            cout<<(it->first)<<" "<<it->second<<endl;
        if (++map[it->second] <= limit)
        {
            res += it->first;
          //cout<<"res = "<<res<<endl;
            n--;
        }
    }
    return res;
}
// Driver code
int main()
{
    vector<int> values = { 5, 3, 7, 1, 2 };
    vector<int> labels = { 5, 7, 7, 7, 6 };
     
    int n = sizeof(values) / sizeof(values[0]);
    int limit = 2;
     
    cout << MaxSumSubset(values, labels,
                         n, limit);
    return 0;
}

# Python3 program to Find subset with
# maximum sum under given condition.
from collections import defaultdict
 
# Function to return the maximum
# sum of the subset
def MaxSumSubset(values, labels,
                 n, limit):
                      
    res = 0
    s = {}
    map = defaultdict(int)
 
    if (n == 0):
        return 0
 
    # Pushing the pair into
    # the multimap
    for i in range(n):
        s[values[i]] = labels[i]
 
    # Traversing the multimap
    # in reverse
    #s = reversed(sorted(s.keys()))
    for it in sorted(s.keys(), reverse = True):
        if n > 0:
            if (map[s[it]] < limit):
                res += it
                #print("res = ",res)
 
                map[s[it]] += 1
 
        n -= 1
 
    return res
 
# Driver code
if __name__ == "__main__":
 
    values = [5, 3, 7, 1, 2]
    labels = [5, 7, 7, 7, 6]
 
    n = len(values)
    limit = 2
 
    print(MaxSumSubset(values, labels,
                       n, limit))
 
# This code is contributed by ukasp

<script>
 
// JavaScript program to Find subset with
// maximum sum under given condition.
 
// Function to return the maximum
// sum of the subset
function MaxSumSubset(values,labels,n,limit)
{
    let res = 0;
    let s=new Map();
    let map=new Map();
  
    if (n == 0)
    {
        return 0;
    }
  
    // Pushing the pair into
    // the multimap
    for (let i = 0; i < n; i++)
    {
        s.set( values[i],
                  labels[i] );
    }
  
    // Traversing the multimap
    // in reverse
    for (let [key,value] of s.entries())
    {
        if(!map.has(value))
            map.set(value,0);
        if (map.get(value) < limit)
        {
            map.set(value,map.get(value)+1);
            res += key;
          //cout<<"res = "<<res<<endl;
            n--;
        }
    }
    return res;
}
 
// Driver code
let values=[5, 3, 7, 1, 2];
let labels=[5, 7, 7, 7, 6];
let n= values.length;
let limit = 2;
document.write(MaxSumSubset(values, labels,n, limit));
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

17

Complejidad de tiempo: O(N), donde N es la longitud de la array.