Chương trình tìm số lượng nhóm tối đa nhận được bánh rán mới bằng Python

Giả sử chúng ta có một giá trị batchSize và một nhóm mảng trong đó nhóm [i] biểu thị rằng có một nhóm khách hàng thuộc nhóm [i] sẽ ghé thăm cửa hàng. Vì vậy, có một cửa hàng bánh rán làm bánh rán theo từng đợt với kích thước batchSize nhất định. Nhưng họ có một quy tắc, họ phải phục vụ tất cả bánh rán của một mẻ trước khi phục vụ bất kỳ bánh rán nào của mẻ tiếp theo. Và mỗi khách hàng sẽ nhận được đúng một chiếc bánh rán. Khi một nhóm vào cửa hàng, tất cả khách hàng của nhóm đó phải được phục vụ trước khi giải quyết bất kỳ nhóm nào tiếp theo. Một nhóm có thể vui mừng nếu tất cả họ đều nhận được bánh rán mới. (Nói cách khác, khách hàng đầu tiên của nhóm không chấp nhận chiếc bánh rán còn sót lại từ nhóm cuối cùng).

Chúng tôi có thể sắp xếp lại các nhóm và cuối cùng chúng tôi phải tìm ra số lượng nhóm hạnh phúc tối đa có thể sau khi sắp xếp lại các nhóm.

Vì vậy, nếu đầu vào giống như batchSize =4 groups =[2,1,8,4,3], thì đầu ra sẽ là 4 vì chúng ta có thể sắp xếp lại chúng như [8,4,2,3,1] nên trước tiên, nhóm thứ hai, thứ ba và thứ tư là hạnh phúc. Chúng tôi có thể làm hai lô bánh rán cho nhóm đầu tiên, một lô cho nhóm thứ hai và làm một lô sau đó phục vụ cho nhóm thứ ba và một cho nhóm thứ tư.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• l:=một danh sách với (g mod batchSize) cho tất cả g trong nhóm

• count:=một bản đồ chứa tần suất các phần tử của l

• g:=danh sách số lượng [i] cho tất cả tôi trong phạm vi 0 thành batchSize

• Định nghĩa một hàm dp (). Điều này sẽ mất sm, t

• nếu tối đa của t bằng 0 thì

  • trả về 0

• ans:=0

• arr:=t

• đối với k trong phạm vi 0 thành batchSize - 1, thực hiện

  • nếu arr [k] giống 0 thì

    • chuyển sang lần lặp tiếp theo

  • arr [k]:=arr [k] - 1

  • ans:=tối đa ans và dp ((sm + k) mod batchSize, arr)

  • arr [k]:=arr [k] + 1

• trả về ans + (1 nếu sm giống 0 nếu không 0)

• Từ phương thức chính trả về dp (0, g)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

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))

Đầu vào

4, [2,1,8,4,3]

Đầu ra

4