Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the goal is that you want to maximize the number of same-sized groups.
There can be multiple correct answers, and you can add to different groups (i.e. you can add 2 to one group, 3 to another, etc.)
Examples: group sizes:[1,1,1], able to add 7 objects Answer: 3, every group already has the same amount
[3,0,2,2,1], able to add 3 objects Answer: 4, you can add 2 objs to the group with 0, and 1 obj to the last group that has 1. So you maximize the 2's.
[5,4,1,3,4], able to add 2 objs Answer: 3, you can either add 1 obj to the group with 3, creating 3 4's, or you can add 1 to each of the groups of 4, creating 3 5's.
I can easily solve this using brute-force (for each number 1...n, where n is the max amount able to be added, try all possible combinations of adding to current groups and adding the number of newly created ones to the original total) but I am confused as to where the algorithmic optimization is. Have a nice day, thanks!
edit: put some example code of what I've tried.
#include <iostream>
#include <vector>
#include <map>
int maxCountOfEqualGroupSize(const std::vector<int>& groups, int objsToAdd) {
int maxGroupCount = 0;
std::map<int,int> groupSizeToGroupCount;
for (const auto& i : groups) {
groupSizeToGroupCount[i]++;
}
//edge case - all groups already have the same size
auto iter = groupSizeToGroupCount.begin();
int firstVal = iter->second;
bool foundDiff = false;
for (; iter != groupSizeToGroupCount.end(); ++iter) {
if (iter->second != firstVal) {
foundDiff = true;
break;
}
}
if (!foundDiff) {
return groups.size();
}
//end edge case
//find biggest value and get that key
//Then advance that key one by one to the right
//for each iteration: start at that key, and start moving left
//filling groups in, once you run out of objs to fill with,
//terminate.
int maxKey;
for (const auto& p : groupSizeToGroupCount) {
if (p.second > maxGroupCount) {
maxGroupCount = p.second;
maxKey = p.first;
}
}
auto startIter = groupSizeToGroupCount.find(maxKey);
auto lastIter = groupSizeToGroupCount.rbegin();
auto firstIter = groupSizeToGroupCount.begin();
for (; startIter->first != lastIter->first; ++startIter) {
int objCounter = objsToAdd;
int runningGroupCount = startIter->second;
auto startPoint = --startIter;
++startIter;
for(auto goingLeft = startPoint;
objCounter >= 0;
--goingLeft) {
int diff = startIter->first - goingLeft->first;
int groupsToFill = goingLeft->second;
int amountToAdd = groupsToFill * diff;
if (amountToAdd > objCounter) {
//add up to what we can, since we can't fill all the groups
while (objCounter >= diff) {
++runningGroupCount;
objCounter -= diff;
}
} else {
objCounter -= amountToAdd;
runningGroupCount += groupsToFill;
}
if (goingLeft == firstIter) {
break;
}
}
maxGroupCount = std::max(maxGroupCount, runningGroupCount);
}
return maxGroupCount;
}
int main() {
std::vector<int> ttt = {1,1,1};
std::vector<int> tt = {3,0,2,2,1};
std::vector<int> t = {5,4,1,3,4};
std::cout << maxCountOfEqualGroupSize(t, 2) << std::endl;
std::cout << maxCountOfEqualGroupSize(tt, 3) << std::endl;
std::cout << maxCountOfEqualGroupSize(ttt, 2) << std::endl;
}
