Find subset with maximum sum under given condition

0 0 5 minutes read

Given values[] and labels[] of n items and a positive integer limit, We need to choose a subset of these items in such a way that the number of the same type of label in the subset should be <= limit and sum of values are maximum among all possible subset choices.

Examples:

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

Approach: The idea is to use a Multimap and Hashmap to solve this problem.

We will store all the values and the respective labels as a pair in the Multimap.
In Multimap the {values, labels} pairs are sorted in increasing order. So, we will traverse the Multimap in reverse to get the pairs in decreasing order.
Now, we will add the values in our answer and store the occurrence of each label in Hashmap to check if the number of occurrences is <= limit.

Below is the implementation of the above approach:

C++

// 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;
}

Java

/*package whatever //do not write package name here */
import java.util.*;
class GFG {
 
  static class Pair
  {
    int first, second;
    public Pair(int first, int second)
    {
      this.first = first;
      this.second = second;
    }
  }
 
  // Function to return the maximum
  // sum of the subset
  static int MaxSumSubset(int[] values, 
                          int[] labels,
                          int n, int limit)
  {
    int res = 0;
    HashSet<Pair> s = new HashSet<>();
    HashMap<Integer, Integer> map = new HashMap<>();
 
    if (n == 0)
    {
      return 0;
    }
 
    // Pushing the pair into 
    // the multimap
    for (int i = 0; i < n; i++)
    {
      s.add(new Pair(values[i],labels[i]));
    }
 
    // Traversing the multimap 
    // in reverse
 
    for(Pair i:s){
      if(!map.containsKey(i.second)){
        map.put(i.second,0);
      }
      if(map.get(i.second)<limit){
        map.put(i.second,map.get(i.second)+1);
        res += i.first;
        n--;
      }
    }
 
    return res;
  }
 
  public static void main (String[] args)
  {
    int[] values = {5, 3, 7, 1, 2 };
    int[] labels = {5, 7, 7, 7, 6 };
 
    int n = values.length;
    int limit = 2;
 
    System.out.println(MaxSumSubset(values, labels,n, limit));
  }
}
 
// This code is contributed by aadityaburujwale.

Python3

# 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

C#

using System;
using System.Collections.Generic;
 
public class GFG {
    public class Pair {
        public int first, second;
        public Pair(int first, int second)
        {
            this.first = first;
            this.second = second;
        }
    }
 
    // Function to return the maximum
    // sum of the subset
    static int MaxSumSubset(int[] values, int[] labels,
                            int n, int limit)
    {
        int res = 0;
        HashSet<Pair> s = new HashSet<Pair>();
        Dictionary<int, int> map
            = new Dictionary<int, int>();
 
        if (n == 0) {
            return 0;
        }
 
        // Pushing the pair into
        // the multimap
        for (int i = 0; i < n; i++) {
            s.Add(new Pair(values[i], labels[i]));
        }
 
        // Traversing the multimap
        // in reverse
 
        foreach(Pair i in s)
        {
            if (!map.ContainsKey(i.second)) {
                map.Add(i.second, 0);
            }
            if (map[i.second] < limit) {
                map[i.second] = map[i.second] + 1;
                res += i.first;
                n--;
            }
        }
 
        return res;
    }
 
    static public void Main()
    {
        int[] values = { 5, 3, 7, 1, 2 };
        int[] labels = { 5, 7, 7, 7, 6 };
 
        int n = values.Length;
        int limit = 2;
 
        Console.WriteLine(
            MaxSumSubset(values, labels, n, limit));
    }
}
// contributed by akashish__

Javascript

<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>

Output:

Time Complexity: O(NlogN), where N is the length of the array, and multimap take O(logN) complexity for insertion and other operations.
Auxiliary Space: O(N), for storing all the elements in the array.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!