โจทย์ข้อ equipped จาก programming.in.th

โจทย์

ความยาก ★★★☆☆

มีของทั้งหมด $N$ ชิ้น แต่ละชิ้นมีราคา $w_i$ ($w_i$ ไม่เกิน 10000) และมีงานทั้งหมด $K$​ ประเภท ($K$​ ไม่เกิน 8) ของแต่ละชิ้นจะบอกว่าสามารถใช้ทำงานประเภทไหนได้บ้าง และทำได้ไม่จำกัดครั้ง

คุณต้องการจะซื้อของทั้งหมดกี่ชิ้นก็ได้ให้ทำงานได้ทั้ง $K$ ประเภท ถามว่าราคาน้อยที่สุดจากการเลือกซื้อของคือเท่าไหร่เพื่อให้ทำงานได้ครบ

ข้อมูลนำเข้า

บรรทัดแรก : รับจำนวน $N$ และ $K$ แทนจำนวนอุปกรณ์และงานตามลำดับโดยที่ $1\leq N \leq 10,000$ และ $1\leq K \leq 8$

บรรทัดที่ 2 ถึง N + 1 : บรรทัดที่ $i$ ให้รับค่า $w_i$ แทนราคาของอุปกรณ์ตามด้วยเลขอีก $K$ ตัว แทนว่าอุปกรณ์ชิ้นนั้นๆสามารถทำงานไหนได้บ้าง โดยจะมีค่าเป็น 1 ถ้าสามารถทำงานชนิดนั้นๆได้

ข้อมูลส่งออก

จำนวนเงินที่น้อยที่สุดที่สามารถซื้อของที่ทำงานได้ครบทุกอย่าง

ตัวอย่าง

จากตัวอย่างมีอุปกรณ์อยู่ทั้งหมด 5 ชนิด และมีงาน 3 ประเภท เพื่อความง่ายเราจะเรียกว่าเป็นงานประเภท A, B และ C
โดยที่:

ชนิดที่ 1: ราคา 10 ใช้ทำงานประเภท A และ C ได้
ชนิดที่ 2: ราคา 30 ใช้ทำงานประเภท B และ C ได้
ชนิดที่ 3: ราคา 5 ใช้ทำงานประเภท A ได้
ชนิดที่ 4: ราคา 4 ใช้ทำงานประเภท C ได้
ชนิดที่ 5: ราคา 150 ใช้ทำงานได้ทุกประเภทเลย

คำอธิบาย: เราสามารถซื้ออุปกรณ์ชนิดที่ 2 และ 3 เพื่อให้ทำงานได้ครบ โดยจ่ายในราคาแค่ 35 ได้ โดยที่ไม่จำเป็นต้องซื้อชนิดที่ 5 ที่ทำได้ทุกอย่างในราคา 150

---

คำใบ้

จำนวนประเภทของงานมันมีน้อยมากๆ (แค่ 8 เอง) เมื่อเทียบกับค่าอื่นๆที่โจทย์กำหนดให้มา

เอาไปใช้ทำอะไรได้ไหมนะ??

วิเคราะห์โจทย์

ด้วยความว่ามันมีประเภทงานมันมีแค่ 8 แบบ แปลว่ามันมีแค่ 64 รูปแบบของการทำงานเท่านั้น (มาจาก $2^8$ ) ซึ่งเราสามารถเก็บข้อมูลส่วนนี้ได้โดยการใช้แต่ละบิตมาแทนว่า งานไหนทำได้แล้วบ้าง

ยกตัวอย่างว่าถ้า เราสามารถทำงานประเภทที่ 3, 6 และ 7 ได้แล้ว ก็สามารถมาสร้างเป็น Bitmask ได้ดังนี้
โดยให้ 1 แทนว่าสามารถทำงานประเภทไหนได้แล้วบ้าง

การที่แปลงรูปแบบการทำงานเป็นแบบนี้ได้ประโยชน์อยู่ 2 อย่าง

1. เรารู้แล้วว่ารูปแบบเริ่มต้นคือ 00000000 และรูปแบบที่เราต้องการคือ 11111111
2. ในการซื้อของเพิ่ม เราสามารถคำนวณได้ในทันทีว่าทำงานประเภทไหนได้บ้างแล้ว

ยกตัวอย่าง เช่นถ้าเครื่องมือสามารถทำงานประเภท 1, 3 และ 6 ได้ เราก็สามารถแทนด้วยบิตได้ดังนี้

สมมติว่าถ้าเราสามารถทำงานประเภท 1, 2, 5 และ 6 ได้อยู่แล้ว ซึ่งสามารถแทนได้ด้วย

ถ้าเราซื้อของที่ว่ามานี่ แปลว่าเราต้องทำงาน 1, 2, 3, 5 และ 6 ได้แล้ว เพราะมีเครื่องมือสำหรับการทำงานประเภทที่ 3 แล้ว ที่แปลงเป็นบิตได้ว่า

สังเกตว่าถ้าเอามาเทียบกันก็จะเห็นว่า การซื้อของมาเพิ่มก็คือการเอาบิตของสิ่งที่ซื้อมา มาทำ bitwise-or กับที่สิ่งที่เราเคยทำได้แล้วนั่นเอง และการที่เราต้องการทำให้ได้ทุกแบบก็คือการหา combination ที่ทำให้บิตกลายเป็น 1 ทั้งหมด

ทีนี้ปัญหาก็เหลือแค่ว่าจะหาราคาที่น้อยที่สุดในการซื้อยังไง ซึ่งแก้ไม่ยากถ้าเราสามารถกำหนด Dynamic State ให้โจทย์ได้

ข้อนี้มีอุปกรณ์อยู่ $N$ ชิ้นและมี state อยู่ทั้งหมด $2^3 = 8$ แบบ เราสามารถกำหนดให้ $dp[i][j]$ แทน ค่าใช้จ่ายน้อยที่สุดที่เราสามารถทำ state j ได้โดยจากใช้อุปกรณ์ชิ้นที่ i เท่านั้น

จากข้อสังเกตก่อนหน้านี้ที่เรารู้ว่าการซื้อของมันเปลี่ยน state ยังไง
สมมติว่าถ้าเรารู้ว่าค่าใช้จ่ายน้อยสุดในการซื้อของเพื่อให้ได้ state $x$ โดยซื้อจากอุปกรณ์แค่ $1...(i-1)$
หรือ ( $d[i-1,x]$ )

เราจะสามารถคำนวณหาว่า $d[i,y]$ มีค่าเป็นเท่าไหร่ได้จาก

เมื่อ

• $x$ แทน state ก่อนซื้อของ
• $y$ แทน state หลังซื้อของชิ้นที่ i
• $w_i$ แทนราคาของชิ้นที่ i

ซึ่งเราสามารถค่อยๆเอาสมการนี้ไปคำนวณ เพื่อหา Dynamic State ที่ต้องการได้

ลิงก์เพิ่มเติม

โจทย์เต็มข้อ Equipped

https://programming.in.th/tasks/1036

โพสต์ Original ใน Facebook

https://www.facebook.com/share/p/Qzs4ATyk3PRbDxnT/