Chương trình phân phối số nguyên lặp lại trong Python

Mô tả bài toán

Cho mảng nums (tối đa 50 giá trị duy nhất) và mảng quantity (số lượng mỗi khách hàng muốn). Kiểm tra có thể phân phối sao cho: khách i nhận đúng quantity[i] phần tử, tất cả phần tử khách i nhận giống nhau, mọi khách đều hài lòng.

Ví dụ

nums = [5,1,2,2,3,4,4,3,3], quantity = [2,2,3] -> True (khách 1: [2,2], khách 2: [4,4], khách 3: [3,3,3]).

Giải thuật (Backtracking + Counter)

1. Đếm tần suất các giá trị trong nums, sau đó đếm tần suất của các tần suất đó -> cnt.
2. Sắp xếp quantity giảm dần.
3. Đệ quy util(i, cntr): thử gán quantity[i] cho một tần suất >= nó, cập nhật cntr, đệ quy i+1.

Triển khai Python

from collections import Counter

def solve(nums, quantity):
    def util(i, cntr):
        if i == len(quantity):
            return True
        temp_counter = cntr.copy()
        for cnt in cntr:
            if cnt >= quantity[i]:
                temp_counter[cnt] -= 1
                if temp_counter[cnt] == 0:
                    temp_counter.pop(cnt)
                rem = cnt - quantity[i]
                temp_counter[rem] += 1
                if util(i + 1, temp_counter):
                    return True
                temp_counter[rem] -= 1
                if temp_counter[rem] == 0:
                    temp_counter.pop(rem)
                temp_counter[cnt] += 1
        return False
    cnt = Counter(Counter(nums).values())
    quantity.sort(reverse=True)
    return util(0, cnt)

nums = [5, 1, 2, 2, 3, 4, 4, 3, 3]
quantity = [2, 2, 3]
print(solve(nums, quantity))

Đầu vào

[5,1,2,2,3,4,4,3,3], [2,2,3]

Đầu ra

True