สารบัญ:
คำจำกัดความ - ปัญหาเครื่องหลังหมายถึงอะไร
ปัญหาเป้เป็นปัญหาการเพิ่มประสิทธิภาพที่ใช้ในการอธิบายปัญหาและการแก้ไข มันมาจากชื่อของมันจากสถานการณ์ที่มีข้อ จำกัด ในจำนวนของรายการที่สามารถวางไว้ในเป้ขนาดคงที่ ด้วยชุดของรายการที่มีตุ้มน้ำหนักและค่าเฉพาะจุดมุ่งหมายก็เพื่อให้ได้ค่ามากที่สุดเท่าที่จะเป็นไปได้ในเครื่องหลังโดยมีข้อ จำกัด ด้านน้ำหนักของเครื่องเป้
Techopedia อธิบายปัญหาเครื่องหลัง
ปัญหาเป้เป็นตัวอย่างของปัญหาการปรับให้เหมาะสมเชิงผสมหัวข้อในวิชาคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์เกี่ยวกับการค้นหาวัตถุที่ดีที่สุดในกลุ่มของวัตถุ นี่เป็นปัญหาที่ได้รับการศึกษามานานกว่าศตวรรษและเป็นปัญหาตัวอย่างที่ใช้กันทั่วไปในการเพิ่มประสิทธิภาพ combinatorial โดยไม่จำเป็นต้องมีวัตถุที่เหมาะสมที่สุดหรือวิธีการแก้ปัญหาที่ จำกัด ปัญหาสามารถพบได้ในสถานการณ์จริงเช่นการจัดสรรทรัพยากรในข้อ จำกัด ทางการเงินหรือแม้แต่ในการเลือกการลงทุนและพอร์ตการลงทุน นอกจากนี้ยังสามารถพบได้ในสาขาต่าง ๆ เช่นคณิตศาสตร์ประยุกต์ทฤษฎีความซับซ้อนวิทยาการเข้ารหัสลับ combinatorics และวิทยาการคอมพิวเตอร์ มันเป็นปัญหาที่สำคัญที่สุดในการขนส่ง
ในปัญหาเครื่องหลังรายการที่กำหนดมีอย่างน้อยสองคุณลักษณะ - ค่าของรายการซึ่งมีผลต่อความสำคัญและน้ำหนักหรือปริมาณของรายการซึ่งเป็นลักษณะข้อ จำกัด เนื่องจากการค้นหาที่ละเอียดถี่ถ้วนเป็นไปไม่ได้เราสามารถแบ่งปัญหาออกเป็นปัญหาย่อยที่เล็กกว่าและเรียกใช้ซ้ำ สิ่งนี้เรียกว่าโครงสร้างย่อยที่ดีที่สุด ข้อตกลงนี้มีเพียงหนึ่งรายการในแต่ละครั้งและน้ำหนักปัจจุบันยังคงมีอยู่ในเป้ ตัวแก้ไขปัญหาจำเป็นต้องตัดสินใจว่าจะรับไอเทมหรือไม่ขึ้นอยู่กับน้ำหนักที่สามารถยอมรับได้ อย่างไรก็ตามหากเป็นโปรแกรมการคำนวณซ้ำนั้นไม่เป็นอิสระและอาจทำให้เกิดปัญหาได้ นี่คือที่สามารถใช้เทคนิคการเขียนโปรแกรมแบบไดนามิก โซลูชั่นสำหรับแต่ละปัญหาย่อยจะถูกเก็บไว้เพื่อให้การคำนวณจะต้องเกิดขึ้นเพียงครั้งเดียว
