โปรแกรมค้นหาจำนวนคำขอโอนที่สามารถทำได้ใน Python

สมมติว่ามีห้องพักในหอพักจำนวน n ห้องที่มีเลขตั้งแต่ 0 ถึง n-1 นักเรียนในห้องหอพักต้องการย้ายไปอีกห้องหนึ่ง และพวกเขาส่งคำขอหลายรายการให้ทำเช่นนั้น ไม่มีที่นั่งในหอพักที่ว่าง คำขอย้ายจะได้รับการดูแลเฉพาะในกรณีที่นักเรียนคนอื่นเข้ามาแทนที่นักเรียนที่เต็มใจจะย้าย ดังนั้น เมื่อได้รับคำขอ เราต้องหาว่าคำขอจำนวนเท่าใดจึงจะสามารถตอบสนองได้

ดังนั้น หากอินพุตเป็น n =3 คำขอ =[[0,2],[1,0],[2,1]] ผลลัพธ์จะเป็น 3

นักเรียนห้อง 0 ย้ายเข้าห้อง 2

นักเรียนห้อง 1 ย้ายไปห้อง 0

นักเรียนห้อง 2 ย้ายไปห้อง 1

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

• สำหรับ k ในช่วงขนาดคำขอเป็น -1 ลดลง 1 ทำ

  • สำหรับ c ในชุดค่าผสมทั้งหมดของ (0 ถึงขนาดของคำขอและ k) ทำ

    • d :=อาร์เรย์ใหม่ขนาด n ที่มีค่า 0

    • สำหรับแต่ละ i ใน c ทำ

      • d[requests[i, 0]] :=d[requests[i, 0]] - 1

      • d[requests[i, 1]] :=d[requests[i, 1]] + 1

    • หากไม่มีข้อใดใน d เป็นจริง

      • กลับ k

• คืนค่า 0

ตัวอย่าง

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

from itertools import combinations
def solve(n, requests):
   for k in range(len(requests), 0, -1):
      for c in combinations(range(len(requests)), k):
         d = [0] * n
         for i in c:
            d[requests[i][0]] -= 1
            d[requests[i][1]] += 1
         if not any(d):
            return k
   return 0

print(solve(3, [[0,2],[1,0],[2,1]]))

อินพุต

3, [[0,2],[1,0],[2,1]]

ผลลัพธ์

3