1815

1815. Maximum Number of Groups Getting Fresh Donuts (Hard)

There is a donuts shop that bakes donuts in batches of batchSize. They have a rule where they must serve all of the donuts of a batch before serving any donuts of the next batch. You are given an integer batchSize and an integer array groups, where groups[i] denotes that there is a group of groups[i] customers that will visit the shop. Each customer will get exactly one donut.

When a group visits the shop, all customers of the group must be served before serving any of the following groups. A group will be happy if they all get fresh donuts. That is, the first customer of the group does not receive a donut that was left over from the previous group.

You can freely rearrange the ordering of the groups. Return the maximum possible number of happy groups after rearranging the groups.

 

Example 1:

Input: batchSize = 3, groups = [1,2,3,4,5,6]
Output: 4
Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1st, 2nd, 4th, and 6th groups will be happy.

Example 2:

Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6]
Output: 4

 

Constraints:

• 1 <= batchSize <= 9
• 1 <= groups.length <= 30
• 1 <= groups[i] <= 109

Related Topics:
Dynamic Programming

Solution 1. Greedy + DP

Let A be groups, B be batchSize.

Split A into different subsets such that:

• at most one of them can have a sum that is not a multiple of B.
• all others must have a sum that is a multiple of B.

We can greedily use the groups that has remainder 0.

And then greedily match 2 groups that has a sum of remainder 0.

For groups of 3 or more, we need to use DP.

Let dp[cnt] be the maximum number of happy groups given a remainder array cnt.

For a given cnt, we can try using a group with remainder cnt[i], 1 <= i < B.

Assume after using the group, the cnt becomes cnt2. cnt2 is the same as cnt expect cnt2[i] = cnt[i] - 1 for the selected i.

So

dp[cnt] = max( (left == 0) + dp(cnt2, (left - i + B) % B ) | 1 <= i < B )

where left is the number of donuts left in the current batch. left can be derived from the cnt so we don't use it as a state for DP.

// OJ: https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/
// Author: github.com/lzl124631x
// Time: O(N^B)
// Space: O(B)
// Ref: https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/discuss/1140644/C%2B%2B-0-ms%3A-Greedy-%2B-DP
class Solution {
    map<vector<int>, int> dp;
    int dfs(vector<int> &cnt, int left) {
        auto it = dp.find(cnt);
        if (it != end(dp)) return it->second;
        int ans = 0, B = cnt.size();
        for (int i = 1; i < B; ++i) {
            if (--cnt[i] >= 0) ans = max(ans, (left == 0) + dfs(cnt, (B + left - i) % B));
            ++cnt[i];
        }
        return dp[cnt] = ans;
    }
public:
    int maxHappyGroups(int B, vector<int>& A) {
        vector<int> cnt(B);
        int ans = 0;
        for (auto &n : A) {
            n %= B;
            if (n == 0) ++ans;
            else if (cnt[B - n]) {
                --cnt[B - n];
                ++ans;
            } else ++cnt[n];
        }
        return ans + dfs(cnt, 0);
    }
};