在给定条件下查找总和最大的子集

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


// C++ program to Find subset with
// maximum sum under given condition.
#include
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 ( [H TG57] 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++)
{
if (++map[it->second] <= limit)
{
res += it->first;
n--;
}
}
return res;
}
// Driver code
int main()
{
vector< int > values = { 5, 3, 7, 1, 2 };
vector< int [HT G110]
int n = sizeof (values) / sizeof (values[0]);
int limit = 2;
cout << MaxSumSubset(values, labels,
n, limit);
return 0;
}


17