home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

Smallest Sufficient Team ใน Python: หาทีมขนาดเล็กที่สุดครอบคลุมทักษะที่ต้องการ

ได้รายการทักษะที่จำเป็น req_skills และรายการคน people (แต่ละคนมีลิสต์ทักษะ) หาทีมขนาดเล็กที่สุด (ดัชนีคน) ที่รวมกันมีทักษะครบทุกอย่างใน req_skills

ตัวอย่าง

req_skills = ["java","flutter","android"], people = [["java"],["android"],["flutter","android"]] → ทีม [0, 2] (คน 0 มี java, คน 2 มี flutter+android)

ขั้นตอนการแก้ปัญหา (DP + Bitmask)

  1. Map ทักษะ → บิต: skill_to_bit = {skill: i}
  2. dp[mask] = รายการคน ที่ทำให้ได้ทักษะ mask เริ่ม dp[0] = []
  3. วนแต่ละคน: คำนวณ person_mask จากทักษะของเขา
  4. วน dp ที่มีอยู่: new_mask = mask | person_mask ถ้า new_mask ไม่มี หรือทีมใหม่สั้นกว่า → อัปเดต
  5. คืน dp[(1< (Mask ที่มีทุกบิตเป็น 1)

การติดตั้งใน Python


class Solution:
    def smallestSufficientTeam(self, req_skills, people):
        skill_to_bit = {s: i for i, s in enumerate(req_skills)}
        dp = {0: []}
        for i, p in enumerate(people):
            person_mask = 0
            for skill in p:
                person_mask |= 1 << skill_to_bit[skill]
            for mask, team in list(dp.items()):
                new_mask = mask | person_mask
                if new_mask == mask:
                    continue
                if new_mask not in dp or len(dp[new_mask]) > len(team) + 1:
                    dp[new_mask] = team + [i]
        return dp[(1 << len(req_skills)) - 1]

ob = Solution()
print(ob.smallestSufficientTeam(
    ["java","flutter","android"],
    [["java"],["android"],["flutter","android"]]
))  # [0, 2]

อินพุต / เอาต์พุต

Input: req_skills=["java","flutter","android"], people=[["java"],["android"],["flutter","android"]]
Output: [0, 2]