Find subset with maximum sum under given condition
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
- 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:
17
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.