โปรแกรมแจกจ่ายจำนวนเต็มซ้ำใน Python

มีอาร์เรย์ nums (ค่า unique ≤ 50) และ quantity[i] = จำนวนที่ลูกค้า i สั่ง ต้องแจกจ่ายให้:

• ลูกค้า i ได้ quantity[i] ชิ้นพอดี
• ค่าที่ลูกค้า i ได้ ต้องเหมือนกันทุกชิ้น
• ลูกค้าทุกคนพอใจ

ตัวอย่าง: nums=[5,1,2,2,3,4,4,3,3], quantity=[2,2,3] ผลลัพธ์ True

วิธีแก้ปัญหา (Backtracking บนความถี่ของความถี่)

1. cnt := Counter(Counter(nums).values()) (นับว่าแต่ละความถี่มีกี่ค่า)
2. เรียง quantity มากไปน้อย
3. DFS/Backtracking ลองจัดสรร quantity[i] ให้แต่ละความถี่

ตัวอย่างโค้ด

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

อินพุต

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

เอาต์พุต

True