เมื่อพิจารณาทั้งน้ำหนักและกำไรของสินค้า N รายการแล้ว เราต้องการนำสินค้าเหล่านี้ใส่ในเป้ซึ่งมีความจุ C เป้าหมายคือการได้รับผลกำไรสูงสุดจากสินค้าในเป้ แต่ละรายการสามารถเลือกได้เพียงครั้งเดียว เนื่องจากเราไม่มีจำนวนสินค้าหลายรายการ
ตัวอย่าง:
- รายการ: [A, B, C, D]
- น้ำหนัก: [2, 3, 1, 4]
- กำไร: [4, 5, 3, 7]
- ความจุ: 5
ลองใช้ชุดค่าผสมที่น้ำหนักรวมน้อยกว่าความจุ 5:
- A + B (น้ำหนักรวม: 5) = กำไร 9
- C + D (น้ำหนักรวม: 5) = กำไร 10
- B + C (น้ำหนักรวม: 4) = 8 กำไร
วิธีแก้ปัญหาพื้นฐาน
การเขียนโปรแกรมแบบไดนามิกจากบนลงล่างพร้อมการจดจำ
เราสามารถใช้การท่องจำเพื่อเอาชนะปัญหาย่อยที่ทับซ้อนกันได้ ย้ำอีกครั้งว่าการจำคือเมื่อเราเก็บผลลัพธ์ของปัญหาย่อยที่แก้ไขไปก่อนหน้านี้ทั้งหมด และส่งคืนผลลัพธ์จากหน่วยความจำหากเราพบปัญหาที่ได้รับการแก้ไขแล้ว
เนื่องจากเรามีค่าที่เปลี่ยนแปลงสองค่า (capacity
และ currentIndex
) ในฟังก์ชันการเรียกซ้ำ knapsackRecursive()
เราจึงสามารถใช้อาร์เรย์สองมิติเพื่อจัดเก็บผลลัพธ์ของปัญหาย่อยทั้งหมดที่แก้ไขได้ ตามที่กล่าวไว้ข้างต้น เราจำเป็นต้องจัดเก็บผลลัพธ์สำหรับทุกอาร์เรย์ย่อย (เช่น สำหรับทุกดัชนีที่เป็นไปได้ 'i') และสำหรับทุกความจุที่เป็นไปได้ 'c'
การเขียนโปรแกรมแบบไดนามิกจากล่างขึ้นบน
ลองเติมอาร์เรย์ dp[][]
ของเราจากโซลูชันด้านบน โดยทำงานจากล่างขึ้นบน โดยพื้นฐานแล้ว เราต้องการค้นหาผลกำไรสูงสุดสำหรับทุกอาร์เรย์ย่อยและทุกความจุที่เป็นไปได้
ซึ่งหมายความว่า dp[i][c]
จะแสดงกำไรกระเป๋าเป้สะพายหลังสูงสุดสำหรับความจุ 'c' ที่คำนวณจากรายการ 'i' รายการแรก
พาร์ติชั่นผลรวมเซ็ตย่อยที่เท่ากัน - Leetcode #416
ปัญหานี้เป็นไปตาม 0/1 รูปแบบกระเป๋าเป้สะพายหลัง วิธีแก้แบบเดรัจฉานแบบพื้นฐานคือลองใช้การแบ่งตัวเลขที่กำหนดออกเป็นสองชุดรวมกันเพื่อดูว่าชุดคู่ใดมีผลรวมเท่ากันหรือไม่
สมมติว่า S
แทนผลรวมของตัวเลขที่กำหนดทั้งหมด ดังนั้นชุดย่อยที่เท่ากันทั้งสองชุดจะต้องมีผลรวมเท่ากับ S/2
สิ่งนี้จะเปลี่ยนปัญหาของเราเป็น: 'ค้นหาเซตย่อยของตัวเลขที่กำหนดซึ่งมีผลรวมเป็น S/2
'
การเขียนโปรแกรมแบบไดนามิกจากล่างขึ้นบน
ลองเติมอาร์เรย์ dp[][]
ของเราจากโซลูชันด้านบน โดยทำงานจากล่างขึ้นบน โดยพื้นฐานแล้ว เราต้องการหาว่าเราสามารถสร้างผลรวมที่เป็นไปได้ทั้งหมดกับทุกเซตย่อยได้หรือไม่ ซึ่งหมายความว่า dp[i][s]
จะเป็น 'จริง' ถ้าเราสามารถสร้างผลรวม 's' จากตัวเลข 'i' ตัวแรกได้
ดังนั้น สำหรับแต่ละตัวเลขที่ดัชนี 'i' (0 ‹= i ‹ num.length) และผลรวม 's' (0 ‹= s ‹= S/2) เรามีสองทางเลือก:
- ไม่รวมหมายเลข ในกรณีนี้ เราจะดูว่าเราสามารถรับ 's' จากเซตย่อยได้หรือไม่ โดยไม่รวมตัวเลขนี้:
dp[i-1][s]
- รวมตัวเลขหากค่าของมันไม่เกิน 's' ในกรณีนี้ เราจะดูว่าเราสามารถหาเซตย่อยเพื่อรับผลรวมที่เหลือได้หรือไม่:
dp[i-1][s-num[i]]
หากสถานการณ์ใดสถานการณ์หนึ่งข้างต้นเป็นจริง เราสามารถค้นหาชุดย่อยของตัวเลขที่มีผลรวมเท่ากับ 's'
ผลรวมย่อย
เมื่อกำหนดชุดของจำนวนบวก ให้พิจารณาว่ามีเซตย่อยที่ผลรวมเท่ากับจำนวน 'S' ที่กำหนดหรือไม่
ตัวอย่าง:
- อินพุต [1, 2, 3, 7]
- S = 6
- เอาท์พุต — — จริง
ปัญหานี้เป็นไปตาม รูปแบบ Knapsack 0/1 และค่อนข้างคล้ายกับพาร์ติชั่นผลรวมเซ็ตย่อยที่เท่ากัน วิธีแก้แบบเดรัจฉานพื้นฐานคือลองใช้ชุดย่อยทั้งหมดของตัวเลขที่กำหนดเพื่อดูว่าชุดใดมีผลรวมเท่ากับ "S"
การเขียนโปรแกรมแบบไดนามิกจากล่างขึ้นบน
เราจะพยายามค้นหาว่าเราสามารถสร้างผลรวมที่เป็นไปได้ทั้งหมดกับทุกเซ็ตย่อยเพื่อเติมอาร์เรย์ dp[TotalNumbers][S+1]
ได้หรือไม่
สำหรับทุกผลรวมที่เป็นไปได้ (โดยที่ 0 ‹= s ‹= S) เรามีสองทางเลือก:
- ไม่รวมหมายเลข ในกรณีนี้ เราจะดูว่าเราสามารถหาผลรวม 's' จากเซตย่อยโดยไม่รวมตัวเลขนี้ =›
dp[index-1][s]
- รวมตัวเลขหากค่าของมันไม่เกิน 's' ในกรณีนี้ เราจะดูว่าเราสามารถหาเซตย่อยเพื่อรับผลรวมที่เหลือได้หรือไม่ =›
dp[index-1][s-num[index]]
ผลรวมผลรวมย่อยขั้นต่ำ
เมื่อกำหนดชุดของจำนวนบวก ให้แบ่งเซตออกเป็นสองชุดย่อยโดยมีค่าความแตกต่างขั้นต่ำระหว่างผลรวมของชุดย่อย
โซลูชั่นพื้นฐาน
สมมติว่า S1 และ S2 เป็นเซตย่อยที่ต้องการสองชุด วิธีแก้ปัญหาแบบ brute-force พื้นฐานคือลองเพิ่มแต่ละองค์ประกอบใน S1 หรือ S2 เพื่อค้นหาชุดค่าผสมที่ให้ผลรวมขั้นต่ำระหว่างสองชุด
การเขียนโปรแกรมแบบไดนามิกจากบนลงล่างพร้อมการจดจำ
เราจะใช้อาร์เรย์สองมิติเพื่อจัดเก็บผลลัพธ์ของปัญหาย่อยที่แก้ไขแล้ว เราสามารถระบุปัญหาย่อยได้โดยไม่ซ้ำกันจาก 'currentIndex' และ 'Sum1'; เพราะ ‘Sum2’ จะเป็นผลรวมของตัวเลขที่เหลือเสมอ
จากล่างขึ้นบน
สมมติว่า 'S' แทนผลรวมของตัวเลขทั้งหมด ดังนั้นสิ่งที่เราพยายามทำให้สำเร็จในปัญหานี้คือการหาเซตย่อยที่ผลรวมใกล้เคียงกับ 'S/2' มากที่สุด เพราะหากเราสามารถแบ่งเซตที่กำหนดออกเป็นสองเซตย่อยที่มีผลรวมเท่ากัน เราจะได้ค่าความแตกต่างขั้นต่ำ นั่นคือศูนย์ สิ่งนี้เปลี่ยนปัญหาของเราเป็น ผลรวมเซตย่อย โดยที่เราพยายามค้นหาเซตย่อยที่ผลรวมเท่ากับตัวเลขที่กำหนด - 'S/2' ในกรณีของเรา หากเราไม่พบสับเซตดังกล่าว เราจะนำสับเซตที่มีผลรวมใกล้เคียง 'S/2' มากที่สุด สิ่งนี้เป็นไปได้อย่างง่ายดาย เนื่องจากเราจะคำนวณผลรวมที่เป็นไปได้ทั้งหมดกับทุกเซตย่อย
โดยพื้นฐานแล้ว เราจำเป็นต้องคำนวณผลรวมที่เป็นไปได้ทั้งหมดจนถึง "S/2" สำหรับตัวเลขทั้งหมด แล้วเราจะเติมอาร์เรย์ db[TotalNumbers][S/2+1]
จากล่างขึ้นบนได้อย่างไร?
สำหรับทุกผลรวมที่เป็นไปได้ (โดยที่ 0 ‹= s ‹= S/2) เรามีสองทางเลือก:
- ไม่รวมหมายเลข ในกรณีนี้ เราจะดูว่าเราสามารถหาผลรวม 's' จากเซตย่อยโดยไม่รวมตัวเลขนี้ =›
dp[index-1][s]
- รวมตัวเลขหากค่าของมันไม่เกิน 's' ในกรณีนี้ เราจะดูว่าเราสามารถหาเซตย่อยเพื่อรับผลรวมที่เหลือได้หรือไม่ =›
dp[index-1][s-num[index]]
หากสถานการณ์ใดสถานการณ์หนึ่งข้างต้นเป็นจริง เราสามารถค้นหาเซตย่อยที่มีผลรวมเท่ากับ 's' เราควรเจาะลึกเรื่องนี้ก่อนจึงจะสามารถเรียนรู้วิธีหาเซตย่อยที่ใกล้เคียงที่สุดได้
จำนวนผลรวมย่อย
เมื่อกำหนดชุดของจำนวนบวก ให้ค้นหาจำนวนชุดย่อยทั้งหมดซึ่งผลรวมเท่ากับจำนวน 'S' ที่ระบุ
จากบนลงล่าง
จากล่างขึ้นบน
เราจะพยายามค้นหาว่าเราสามารถสร้างผลรวมที่เป็นไปได้ทั้งหมดกับทุกเซ็ตย่อยเพื่อเติมอาร์เรย์ db[TotalNumbers][S+1
] หรือไม่
ดังนั้น ในทุกขั้นตอน เรามีสองทางเลือก:
- ไม่รวมหมายเลข นับชุดย่อยทั้งหมดที่ไม่มีหมายเลขที่กำหนดจนถึงผลรวมที่กำหนด =›
dp[index-1][sum]
- รวมตัวเลขหากค่าของมันไม่เกิน 'ผลรวม' ในกรณีนี้ เราจะนับเซตย่อยทั้งหมดเพื่อให้ได้ผลรวมที่เหลือ =›
dp[index-1][sum-num[index]]
หากต้องการค้นหาชุดผลรวม เราจะบวกทั้งสองค่าจากสองค่าข้างต้น:
dp[index][sum] = dp[index-1][sum] + dp[index-1][sum-num[index]])
ผลรวมเป้าหมาย
ลีทโค้ด #494
กำหนดชุดตัวเลขบวก (ไม่ใช่ศูนย์) และผลรวมเป้าหมาย 'S' แต่ละหมายเลขควรมีเครื่องหมาย '+' หรือ '-' เราจำเป็นต้องหาวิธีทั้งหมดในการกำหนดสัญลักษณ์เพื่อสร้างผลรวมของตัวเลขให้เท่ากับเป้าหมาย 'S'
เราถูกขอให้ค้นหาชุดย่อยสองชุดของตัวเลขที่กำหนดซึ่งความแตกต่างเท่ากับเป้าหมายที่กำหนด 'S' สมมติว่า 'Sum(s1)' หมายถึงผลรวมของชุด 's1' และ 'Sum(s2)' หมายถึงผลรวมของชุด 's2' ดังนั้นสมการที่ต้องการคือ:
Sum(s1) - Sum(s2) = S
สมการนี้สามารถลดลงเป็นปัญหาผลรวมเซตย่อยได้ สมมติว่า 'ผลรวม (ตัวเลข)' หมายถึงผลรวมของตัวเลขทั้งหมด ดังนั้น:
Sum(s1) + Sum(s2) = Sum(num)
ลองเพิ่มสมการสองสมการข้างต้น:
=> Sum(s1) - Sum(s2) + Sum(s1) + Sum(s2) = S + Sum(num)
=> 2 * Sum(s1) = S + Sum(num)
=> Sum(s1) = (S + Sum(num)) / 2
สิ่งนี้จะแปลงปัญหาของเราเป็น: "ค้นหาจำนวนชุดย่อยของตัวเลขที่กำหนดซึ่งผลรวมเท่ากับ"
=> (S + Sum(num)) / 2