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 subsetint 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 codeint 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 subsetdef 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 codeif __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 subsetfunction 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 codelet 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.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Here you will find 17177 more Information to that Topic: geeksforgeeks.org/find-subset-with-maximum-sum-under-given-condition/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/find-subset-with-maximum-sum-under-given-condition/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/find-subset-with-maximum-sum-under-given-condition/ […]