กระเป๋า 0/1: เลือกหรือไม่เลือก
เพิ่มมูลค่าให้สูงสุดภายใต้ขีดจำกัดน้ำหนัก
กระเป๋า 0/1: เลือกหรือไม่เลือก เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เรื่องราวของปัญหากระเป๋า
คุณมีกระเป๋าที่รับน้ำหนักได้จำกัดและกองสิ่งของอยู่ ปัญหา กระเป๋าแบบ 0/1 ถามว่า สิ่งของใดให้มูลค่ารวมสูงสุดโดยไม่บรรจุเกินความจุ 🎒
เลือกหรือข้าม
คำว่า 0/1 หมายความว่าสิ่งของแต่ละชิ้นจะถูกเลือกทั้งหมดหรือข้ามทั้งหมด คุณไม่สามารถหยิบสิ่งของเพียงครึ่งชิ้นได้ ดังนั้นทุกทางเลือกจึงมีเพียงใช่หรือไม่ใช่
เหตุใดวิธีโลภจึงใช้ไม่ได้
การหยิบสิ่งของที่ราคาถูกที่สุดหรือมีมูลค่าสูงที่สุดก่อนอาจทำให้เสียความจุไปโดยเปล่าประโยชน์ วิธีลัดแบบ โลภ ใช้ไม่ได้กับปัญหานี้ คุณจึงต้องพิจารณาชุดผสมที่เป็นไปได้จริง
ข้อมูลนำเข้าสองชุด
คุณได้รับรายการสองชุดที่สอดคล้องกัน ได้แก่ น้ำหนักและมูลค่าของสิ่งของแต่ละชิ้น พร้อมความจุหนึ่งค่า สิ่งของ i มีน้ำหนัก wt[i] และมูลค่า val[i]
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7กำหนดสถานะ
ให้ dp[i][w] เป็นมูลค่าที่ดีที่สุดจากการใช้สิ่งของ i ชิ้นแรกภายใต้ความจุ w การตั้งชื่อสถานะให้แม่นยำคือหัวใจสำคัญทั้งหมด
ทางเลือกในการข้าม
หากคุณ ข้าม สิ่งของ i มูลค่าจะเท่ากับค่าที่มีอยู่แล้ว: dp[i-1][w] ความจุจะยังคงเดิมสำหรับสิ่งของที่เหลือ
ทางเลือกในการเลือก
หากคุณ เลือก สิ่งของ i ให้บวกมูลค่าของสิ่งของนั้นและลดความจุลง: val[i] + dp[i-1][w - wt[i]] การคำนวณนี้ทำได้เมื่อ w มีค่าอย่างน้อย wt[i] เท่านั้น
เลือกทางเลือกที่ดีกว่า
ความสัมพันธ์เวียนเกิดจะเก็บค่าที่มากกว่าจากสองทางเลือกด้วย max แต่ละช่องจะอาศัยคำตอบที่คำนวณไว้แล้วในช่องด้านล่าง
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])แถวฐาน
เมื่อไม่มีสิ่งของ คุณจะใส่มูลค่าได้เป็นศูนย์ไม่ว่าความจุจะเท่าใด กรณีฐาน นี้จะเติมแถวแรกด้วยศูนย์ทั้งหมดเพื่อใช้เป็นจุดเริ่มต้น
dp = [[0] * (cap + 1) for _ in range(n + 1)]เติมตาราง
วนสิ่งของในรอบนอก และวนความจุในรอบใน แต่ละช่องจะอ่านเฉพาะแถวด้านบน ดังนั้นการกวาดผ่านเพียงครั้งเดียวก็ เติม ทุกช่องได้
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]อ่านคำตอบ
ช่องขวาล่าง dp[n][cap] เก็บมูลค่าสูงสุดของสิ่งของทั้งหมดภายใต้ความจุเต็ม ช่องเดียวนี้คือคำตอบสุดท้าย
ตรวจสอบอย่างรวดเร็ว
ทดสอบความสัมพันธ์เวียนเกิดหลักของปัญหากระเป๋าแบบ 0/1
ทบทวน
คุณได้เรียนรู้ปัญหากระเป๋าแบบ 0/1 แล้ว: สิ่งของแต่ละชิ้นมีทางเลือกคือเลือกหรือข้าม dp[i][w] เก็บค่าที่ดีที่สุดระหว่างการข้ามกับการเลือก และ dp[n][cap] คือคำตอบ 🎉
คำถามที่พบบ่อย
บทเรียน “กระเป๋า 0/1: เลือกหรือไม่เลือก” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “กระเป๋า 0/1: เลือกหรือไม่เลือก” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “กระเป๋า 0/1: เลือกหรือไม่เลือก”
เพิ่มมูลค่าให้สูงสุดภายใต้ขีดจำกัดน้ำหนัก คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “กระเป๋า 0/1: เลือกหรือไม่เลือก” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- กระเป๋า 0/1: เลือกหรือไม่เลือก
- กระเป๋าที่ปรับปรุงการใช้พื้นที่
- DP แบบไม่จำกัดจำนวนและการทอนเหรียญ
- ผลรวมเซตย่อยและการแบ่งส่วน