資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時裝研究
法律研究使用 Python 查詢獲得新鮮甜甜圈的最多組數的程式
假設我們有一個值 batchSize 和一個數組 group，其中 groups[i] 表示有一組 groups[i] 顧客將訪問商店。所以有一家甜甜圈店，以給定的 batchSize 為單位烘焙甜甜圈。但他們有一個規則，他們必須在提供下一批甜甜圈之前提供完一批甜甜圈。每個顧客將得到一個甜甜圈。當一組進入商店時，必須在處理任何下一組之前為該組的所有顧客提供服務。如果所有成員都得到新鮮的甜甜圈，一個組可能會很開心。（換句話說，該組的第一位顧客不接受上一組剩餘的甜甜圈。）
我們可以重新排列這些組，最後我們必須在重新排列這些組之後找到儘可能多的快樂組。
因此，如果輸入為 batchSize = 4 groups = [2,1,8,4,3]，則輸出將為 4，因為我們可以將它們重新排列為 [8,4,2,3,1]，因此第一、第二、第三和第四組都很高興。我們可以為第一組製作兩批甜甜圈，為第二組製作一批甜甜圈，製作一批然後提供給第三組，為第四組製作一批。
要解決這個問題，我們將遵循以下步驟 -
l := 一組包含所有組中 g 的（g mod batchSize）
count := 一個包含 l 元素頻率的對映
g := 一個包含 range 0 到 batchSize 中所有 i 的 count[i] 的列表
定義一個函式 dp()。它將使用 sm、t
如果 t 的最大值與 0 相同，則
返回 0
ans := 0
arr := t
進行 0 到 batchSize - 1 的迴圈，執行
如果 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))輸入
4, [2,1,8,4,3]
輸出
4
104 次檢視
