กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ
อนุมานสมการเวียนเกิดของกระเป๋าเป้ 0/1 เติมตารางสองมิติ แล้วลดรูปเป็นอาร์เรย์หนึ่งมิติด้วยการวนความจุจากมากไปน้อย
กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ เป็นบทเรียน DSA Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน DSA Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหากระเป๋าเป้ 0/1
ปัญหา กระเป๋าเป้ 0/1: กำหนดให้มีสิ่งของ n ชิ้น โดยแต่ละชิ้นมีน้ำหนัก w[i] และมูลค่า v[i] รวมถึงกระเป๋าเป้ที่มีความจุ W ให้เลือกสิ่งของเพื่อทำให้มูลค่ารวมสูงสุดโดยไม่เกินความจุ สิ่งของแต่ละชิ้นจะถูกเลือกได้เพียงครั้งเดียว (0 = ไม่เลือก, 1 = เลือก) นี่คือต้นแบบสำคัญของปัญหา DP ในการสัมภาษณ์จำนวนมาก รวมถึงปัญหาการแบ่งเซตย่อยให้ผลรวมเท่ากันและผลรวมเป้าหมาย
สถานะ DP และสมการเวียนเกิด
กำหนดให้ dp[i][c] เป็นมูลค่าสูงสุดที่ทำได้โดยใช้สิ่งของ i ชิ้นแรกและมีความจุ c สำหรับสิ่งของ i มีทางเลือกสองแบบ: ไม่เลือก (dp[i-1][c]) หรือ เลือก หาก w[i] <= c (dp[i-1][c-w[i]] + v[i]) สมการเวียนเกิดคือ dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) เมื่อ w[i] <= c มิฉะนั้น dp[i][c] = dp[i-1][c] กรณีฐานคือ dp[0][c] = 0 สำหรับทุกค่า c
การใช้งานตาราง DP แบบ 2 มิติ
ตาราง 2 มิติมีรายการทั้งหมด (n+1) x (W+1) รายการ และเติมค่าทีละแถวสำหรับสิ่งของแต่ละชิ้น เมื่อเติมค่าครบทุกแถวแล้ว dp[n][W] จะเก็บมูลค่าสูงสุดไว้ การทำงานนี้ใช้เวลา O(n × W) และใช้หน่วยความจำ O(n × W) — เป็นความซับซ้อนแบบกึ่งพหุนามที่มีประสิทธิภาพเมื่อ W มีค่าน้อย
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10เหตุใดจึงวนความจุย้อนกลับสำหรับ DP 1 มิติ
ข้อสังเกตสำคัญคือ แถว i ขึ้นอยู่กับแถว i-1 เท่านั้น ดังนั้นเราจึงใช้อาร์เรย์ 1 มิติ เพียงอาร์เรย์เดียว และอัปเดตค่าในอาร์เรย์เดิมได้ อย่างไรก็ตาม หากวนค่าความจุ c จากซ้ายไปขวา (จากน้อยไปมาก) สิ่งของ i อาจถูกนับซ้ำสองครั้ง เพราะเราอาจใช้ค่าที่อัปเดตแล้วของ c-w[i] ซึ่งรวมสิ่งของ i อยู่ก่อนแล้ว การวน จากขวาไปซ้าย (จากมากไปน้อย) ทำให้มั่นใจได้ว่าสิ่งของแต่ละชิ้นจะถูกใช้มากที่สุดหนึ่งครั้งในการอัปเดตแต่ละแถว
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous rowการใช้งานแบบ 1 มิติที่ลดการใช้หน่วยความจำ
ด้วยการเก็บไว้เพียงอาร์เรย์เดียวและวนค่าความจุจาก W ลงไปจนถึง w[i] เราจะได้ผลลัพธ์เดียวกับตาราง 2 มิติ โดยใช้หน่วยความจำเพียง O(W) ความซับซ้อนด้านเวลายังคงเป็น O(n × W) การลดการใช้หน่วยความจำนี้เป็นสิ่งสำคัญที่ควรจดจำ — ผู้สัมภาษณ์มักขอให้คุณลดปัญหากระเป๋าเป้ 2 มิติเป็น 1 มิติ
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10การกู้คืนรายการสิ่งของที่มีสถานะ selected
หากต้องการค้นหาว่า สิ่งของใดมีสถานะ selected คุณต้องใช้ตาราง 2 มิติทั้งหมด หลังจากเติมค่าจนครบแล้ว ให้เริ่มจาก dp[n][W] และไล่ย้อนกลับ: หาก dp[i][c] != dp[i-1][c] แสดงว่าสิ่งของ i ถูกเลือกไว้ — ให้ลบน้ำหนักของสิ่งของนั้นออกจาก c แล้วเลื่อนไปยังแถว i-1 ทำต่อไปจนกระทั่ง i = 0 การลดรูปเป็น 1 มิติจะทิ้งความสามารถในการกู้คืนรายการนี้ไป
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
w, v = weights[i-1], values[i-1]
for c in range(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))ตัวอย่างเชิงปฏิบัติ: ทำให้มูลค่ารวมสูงสุด
พิจารณาสิ่งของต่อไปนี้: weights=[2,3,4,5], values=[3,4,5,6], W=8 ทางเลือกที่ดีที่สุดคือเลือกสิ่งของที่มีน้ำหนัก 3 (มูลค่า 4) และน้ำหนัก 5 (มูลค่า 6) — น้ำหนักรวม 8 และมูลค่ารวม 10 หรือเลือกสิ่งของน้ำหนัก 2 และ 5 — มูลค่ารวม 9 หรือเลือกสิ่งของน้ำหนัก 2 และ 3 — มูลค่า 7 วิธี DP จะหาค่าสูงสุด 10 ได้อย่างถูกต้อง สังเกตว่าวิธีแบบละโมบ (เลือกอัตราส่วนมูลค่าต่อน้ำหนักสูงสุดก่อน) จะเลือกสิ่งของที่มีอัตราส่วน 1.5 ก่อน (น้ำหนัก 2 มูลค่า 3) — แต่ไม่ได้ให้ผลดีที่สุดเสมอไป
กระเป๋าเป้แบบแบ่งส่วนเทียบกับกระเป๋าเป้ 0/1
ในกระเป๋าเป้แบบแบ่งส่วน คุณสามารถเลือกสิ่งของเพียงบางส่วนได้ ปัญหานี้แก้ได้ด้วยวิธีแบบละโมบ โดยเรียงสิ่งของตามอัตราส่วนมูลค่าต่อน้ำหนัก ในกระเป๋าเป้ 0/1 สิ่งของไม่สามารถแบ่งได้ — วิธีแบบละโมบจึงใช้ไม่ได้ และต้องใช้ DP ผู้สัมภาษณ์ใช้ความแตกต่างนี้เพื่อทดสอบว่าคุณทราบหรือไม่ว่าวิธีแบบละโมบใช้ได้ในกรณีใด หากถูกถามถึงรูปแบบแบ่งส่วน ให้กล่าวถึงวิธีแบบละโมบร่วมกับการเรียงลำดับทันที แต่หากเป็นรูปแบบ 0/1 ให้เลือกใช้ DP
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))ความซับซ้อนด้านเวลาแบบกึ่งพหุนาม
ปัญหากระเป๋าเป้ 0/1 เป็นปัญหา NP-สมบูรณ์ แต่เรากลับแก้ได้ในเวลา O(nW) ความขัดแย้งนี้อธิบายได้เพราะ O(nW) เป็นความซับซ้อนแบบ กึ่งพหุนาม: W เป็นค่า ไม่ใช่ขนาดข้อมูลนำเข้า การแทนค่า W ในระบบฐานสองใช้บิต O(log W) ดังนั้นความซับซ้อนที่แท้จริงคือ O(n × 2^(log W)) ซึ่งเป็นเลขชี้กำลังเมื่อเทียบกับขนาดข้อมูลนำเข้า เมื่อ W มีค่าน้อย (เช่น 10⁴) DP จะใช้งานได้จริง แต่เมื่อ W อาจมีค่าเป็น 10⁹ เราจำเป็นต้องใช้แนวทางอื่น
คำถามต่อจากผู้สัมภาษณ์: ความจุขนาดใหญ่
หากผู้สัมภาษณ์กำหนดให้ W มีค่ามากมาก (เช่น 10⁹) แต่ n มีค่าน้อย DP มาตรฐานจะใช้ไม่ได้ ทางเลือกอื่นได้แก่: (1) วิธีแบ่งครึ่งแล้วพบกัน ใช้เวลา O(2^(n/2) × n), (2) การประมาณคำตอบแบบละโมบสำหรับรูปแบบแบ่งส่วน หรือ (3) การแบ่งแขนงและจำกัดขอบเขต สำหรับโจทย์สัมภาษณ์ส่วนใหญ่ที่มี W <= 10⁵ คำตอบที่คาดหวังคือ DP 1 มิติที่วนย้อนกลับ
วิธีแบ่งครึ่งแล้วพบกันสำหรับความจุขนาดใหญ่
เมื่อ W มีค่ามากมากแต่ n มีค่าน้อย (เช่น n=40) DP มาตรฐานที่ใช้เวลา O(nW) จะไม่สามารถใช้งานได้ แต่การไล่ตรวจครบทั้ง 2^n กรณีก็ช้าเกินไป วิธีแบ่งครึ่งแล้วพบกัน จะแบ่งสิ่งของออกเป็นสองครึ่ง สร้างเซตย่อยทั้งหมด 2^(n/2) เซตสำหรับแต่ละครึ่ง แล้วจับคู่เซตเหล่านั้นให้เหมาะสมที่สุด เรียงครึ่งหนึ่งตามน้ำหนัก จากนั้นใช้การค้นหาแบบทวิภาคสำหรับแต่ละเซตย่อยของอีกครึ่งหนึ่ง เพื่อหาคู่ที่ดีที่สุดภายใต้ความจุ วิธีนี้ใช้เวลา O(2^(n/2) × n) — ใช้งานได้จริงสำหรับ n ไม่เกิน 40
ตรวจสอบความเข้าใจ
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
ทบทวนบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า: DP ของกระเป๋าเป้ 0/1 มีสถานะ dp[i][c] ซึ่งแทนมูลค่าสูงสุดเมื่อมีสิ่งของ i ชิ้นและความจุ c, สมการเวียนเกิดจะเลือกว่าจะไม่เลือกหรือเลือกสิ่งของแต่ละชิ้น, และ การลดการใช้หน่วยความจำเป็น 1 มิติจะวนค่าความจุจากขวาไปซ้ายเพื่อป้องกันการนับสิ่งของซ้ำ บทถัดไป เราจะสำรวจกระเป๋าเป้แบบไม่จำกัด ซึ่งสามารถนำสิ่งของกลับมาใช้ซ้ำได้ และนำไปประยุกต์กับการทอนเงิน II
คำถามที่พบบ่อย
บทเรียน “กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส DSA Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส DSA Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ”
อนุมานสมการเวียนเกิดของกระเป๋าเป้ 0/1 เติมตารางสองมิติ แล้วลดรูปเป็นอาร์เรย์หนึ่งมิติด้วยการวนความจุจากมากไปน้อย คุณปฏิบัติ DSA Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน DSA Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน DSA Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน DSA Interview Prep นี้ได้ไหม
ได้ บทเรียน DSA Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- กระเป๋าเป้ 0/1 และการลดการใช้หน่วยความจำ
- กระเป๋าเป้ไม่จำกัดจำนวนและการทอนเหรียญ II
- ผลรวมเซตย่อยเท่ากันของการแบ่งพาร์ทิชัน
- ผลรวมเป้าหมายพร้อมเครื่องหมายบวกและลบ