กระเป๋าที่ปรับปรุงการใช้พื้นที่

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

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

เก็บอาร์เรย์ dp เดียวที่มีความยาว cap+1 เมื่อประมวลผลสิ่งของแต่ละชิ้น ให้เขียนทับอาร์เรย์เดิมเพื่อแทนแถวใหม่

หากกวาดความจุจากซ้ายไปขวา dp[w - wt[i]] อาจถูกอัปเดตสำหรับสิ่งของชิ้นเดียวกันไปแล้ว ซึ่งจะทำให้คุณเลือกสิ่งของ i ได้ สองครั้ง

วิธีแก้คือวนความจุจากค่าสูงไปค่าต่ำ การวน ย้อนกลับ รับประกันว่า dp[w - wt[i]] ยังคงเก็บค่าจากรอบของสิ่งของก่อนหน้า

เมื่อคำนวณ dp[w] ดัชนีที่เล็กกว่าอย่าง w - wt[i] จะยัง ไม่ถูกเปลี่ยนแปลง ในรอบนี้ จึงยังสะท้อนค่าจากแถวด้านบนตามที่ต้องการ

ความจุที่น้อยกว่า wt[i] ไม่สามารถใส่สิ่งของชิ้นนี้ได้ ดังนั้นรอบวนซ้ำจึงหยุดที่ wt[i] การข้ามค่าดังกล่าวช่วยประหยัดรอบการทำงานที่ไม่จำเป็น

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

หลังประมวลผลสิ่งของทั้งหมดแล้ว dp[cap] จะเก็บมูลค่าสูงสุดไว้ ซึ่งเป็นตัวเลขเดียวกับที่ตารางสองมิติจะให้ผลลัพธ์ เพียงใช้หน่วยความจำน้อยกว่ามาก

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

เทคนิคนี้ช่วยได้เมื่อ cap มีขนาดใหญ่และตารางสองมิติอาจใช้หน่วยความจำเกิน ขีดจำกัดหน่วยความจำ นี่เป็นเทคนิคพื้นฐานในการแข่งขันที่ควรจดจำ

ทดสอบกฎสำคัญของปัญหากระเป๋าแบบ 1D

คุณลดตารางสองมิติให้เหลืออาร์เรย์เดียว และวนความจุแบบ ย้อนกลับ เพื่อให้ถูกต้อง โดยแลกหน่วยความจำระดับกำลังสองกับเชิงเส้น 🚀