ผลรวมเซตย่อยและการแบ่งส่วน

เมื่อกำหนดตัวเลขและเป้าหมายมาให้ มี เซตย่อยใดที่รวมกันได้ตรงกับเป้าหมายพอดีหรือไม่ ปัญหานี้คือปัญหากระเป๋าที่มูลค่าเท่ากับน้ำหนัก

ในที่นี้คุณติดตามว่าจำนวนเงินใดไปถึงได้ ไม่ใช่ค่าที่มากที่สุด ให้ dp[s] เป็นจริงเมื่อมีเซตย่อยบางชุดรวมกันได้เท่ากับ s พอดี

เซตย่อยว่างมีผลรวมเป็นศูนย์ ดังนั้น dp[0] จึงเริ่มต้นเป็นจริง ผลรวมอื่นทั้งหมดเริ่มต้นเป็นเท็จ จนกว่าจะมีตัวเลขยืนยันว่าไปถึงได้

สำหรับตัวเลขแต่ละตัว ให้ทำเครื่องหมายว่า s ไปถึงได้ หากก่อนหน้านี้ s - num ไปถึงได้แล้ว ตัวเลขหนึ่งตัวสามารถเปลี่ยนผลรวมหลายค่าให้เป็นจริงได้

ตัวเลขแต่ละตัวใช้ได้ไม่เกินหนึ่งครั้ง ดังนั้นรอบด้านในจึงต้องทำงานแบบ ย้อนกลับ เช่นเดียวกับปัญหากระเป๋าแบบ 0/1 หากวนไปข้างหน้า ตัวเลขจะถูกใช้ซ้ำ

หลังประมวลผลตัวเลขทั้งหมดแล้ว dp[target] จะตอบคำถามนี้ ค่าจริงหมายความว่ามีเซตย่อยที่ถูกต้องอยู่ ส่วนค่าเท็จหมายความว่าเป็นไปไม่ได้

ปัญหา การแบ่งส่วน ถามว่า คุณสามารถแบ่งอาร์เรย์ออกเป็นสองส่วนที่มีผลรวมเท่ากันได้หรือไม่ ปัญหานี้ลดรูปเป็นปัญหาผลรวมของเซตย่อยได้โดยตรง

หากผลรวมทั้งหมดเป็นเลขคี่ การแบ่งเป็นสองส่วนเท่ากันย่อมเป็นไปไม่ได้ จึงตอบว่าไม่ทันที มิฉะนั้นเป้าหมายก็คือ total // 2

ตอนนี้เพียงตรวจสอบว่ามีเซตย่อยที่รวมกันได้ถึง total // 2 หรือไม่ หากส่วนหนึ่งมีผลรวมเท่ากับเป้าหมาย ส่วนที่เหลือจะกลายเป็น ส่วนที่สองซึ่งมีผลรวมตรงกันโดยอัตโนมัติ

ต้นทุนอยู่ในระดับ n คูณ target ซึ่งเป็นขอบเขตแบบ กึ่งพหุนาม วิธีนี้ทำงานเร็วเมื่อเป้าหมายมีขนาดเล็ก และช้าเมื่อผลรวมมีขนาดใหญ่มาก

ผลรวมของสับเซต การแบ่งส่วน และปัญหากระเป๋าเป้ 0/1 ใช้กลไกเดียวกัน เมื่อสังเกตรูปแบบ เลือกหรือไม่เลือกได้ คุณก็สามารถนำลูปเดิมกลับมาใช้ซ้ำได้

ทดสอบการลดรูปปัญหาการแบ่งส่วน

คุณแก้ปัญหาผลรวมของสับเซตด้วย DP แบบบูลีนและลูปย้อนกลับ จากนั้นลดรูปปัญหา การแบ่งส่วนให้เหลือการหาผลรวม // 2 กลไกเดิม แต่ได้ผลลัพธ์ใหม่ ✅