在Python中找到获得新甜甜圈的最大组数程序

假设我们有一个值 batchSize 和一个数组 group，其中 groups[i] 表示将有一个由 groups[i] 个客户组成的顾客组来访问商店。所以有一个甜圆饼店，它以给定的 batchSize 进行批量烘焙。但是他们有一个规则，他们必须在服务下一批之前服务完所有批量中的所有甜圆饼。每个客户都会获得一份甜圆饼。当一组进入商店时，必须在处理任何下一组之前为该组中的所有客户服务。如果一组人都享受到新鲜的甜圆饼，他们就会感到高兴。（换句话说，该组的第一个客户不接受上一组留下的甜圆饼）。

我们可以重新排列这些组，并最终找到重新排列后最大可能的快乐小组数。

因此，如果输入为 batchSize=4 groups=[2,1,8,4,3]，那么输出将为4，因为我们可以将它们重新排列为 [8,4,2,3,1] ，所以第一、第二、第三和第四组都很高兴。我们可以为第一组制作两批甜圆饼，为第二组制作一批，然后为第三组制作一批，为第四组制作一批。

为了解决这个问题，我们将按以下步骤进行−

l：对于所有g in groups，具有(g mod batchSize)的列表
个数：包含l元素频率的映射
g：所有i范围内的count[i]列表为0-batchSize
定义一个函数 dp()。这将采用sm，t
如果最大值t与0相同，则
- 返回0
ans：= 0
arr：= t
对于范围为0到batchSize-1的k，进行以下操作
- 如果arr [k]与0相同，则
  - 进入下一次迭代
- arr [k]：= arr [k] – 1
- ans：= ans和dp（（sm + k）mod batchSize，arr）的最大值
- arr [k]：= arr [k] + 1
返回 ans +（1，如sm等于0，否则为0）
从主方法返回dp（0，g）

示例

让我们看一下以下实现，以得到更好的理解

from collections import Counter
def solve(batchSize, groups):
    l = [g % batchSize for g in groups]
    count = Counter(l)
    g = [count[i] for i in range(batchSize)]

    def dp(sm, t):
        if max(t) == 0:
            return 0

        ans, arr =0, list(t)
        for k in range(batchSize):
            if arr[k] == 0:
                continue
            arr[k] -= 1
            ans = max(ans, dp((sm + k) % batchSize, arr))
            arr[k] += 1
        return ans + (sm == 0)

    return dp(0, g)

batchSize = 4
groups = [2,1,8,4,3]
print(solve(batchSize, groups))