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

สมมติว่าเรามีจำนวนอาร์เรย์ มีค่าไม่ซ้ำกันไม่เกิน 50 ค่า นอกจากนี้เรายังมีอาร์เรย์อื่นที่เรียกว่าปริมาณ โดยที่ quantity[i] หมายถึงจำนวนค่าที่ลูกค้าสั่งซื้อ เราต้องตรวจสอบว่าสามารถแจกจ่าย nums ดังกล่าวได้หรือไม่

• ลูกค้าได้รับสินค้าจำนวนที่แน่นอน[i]

• มูลค่าที่ลูกค้าได้รับมีค่าเท่ากัน และ

• ลูกค้าทุกท่านพึงพอใจ

ดังนั้น หากอินพุตเป็น nums =[5,1,2,2,3,4,4,3,3] ปริมาณ =[2,2,3] ผลลัพธ์จะเป็น True เนื่องจากลูกค้าสองคนต้องการองค์ประกอบสองอย่าง ดังนั้นพวกเขาจึงได้ [2,2] และ [4,4] และคนที่สามต้องการสามรายการ พวกเขาสามารถได้รับ [3,3,3] ดังนั้นทุกคนจึงพอใจ

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา i, cntr

• ถ้าฉันเท่ากับขนาดของปริมาณ แล้ว

  • คืนค่า True

• temp_counter :=ทำสำเนาของ cntr

• สำหรับแต่ละ cnt ใน cntr ทำ

  • ถ้า cnt>=ปริมาณ[i] แล้ว

    • temp_counter[cnt] :=temp_counter[cnt] - 1

    • ถ้า temp_counter[cnt] เหมือนกับ 0 แล้ว

      • ลบองค์ประกอบ cnt-th จาก temp_counter

    • rem :=cnt - ปริมาณ[i]

    • temp_counter[rem] :=temp_counter[rem] + 1

    • ถ้า util(i+1, temp_counter) เป็นจริง

      • คืนค่า True

    • temp_counter[rem] :=temp_counter[rem] - 1

    • ถ้า temp_counter[rem] เหมือนกับ 0 แล้ว

      • ลบองค์ประกอบ rem-th จาก temp_counter

  • temp_counter[cnt] :=temp_counter[cnt] + 1

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังนี้

• cnt :=ความถี่ในการถือแผนที่ของความถี่ทั้งหมดที่มีหน่วยเป็น nums

• เรียงลำดับปริมาณในลำดับย้อนกลับ

• return util(0, cnt)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

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

อินพุต

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

ผลลัพธ์

True