เมื่อพิจารณาทั้งน้ำหนักและกำไรของสินค้า 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

ลีทโค้ด #416

ปัญหานี้เป็นไปตาม 0/1 รูปแบบกระเป๋าเป้สะพายหลัง วิธีแก้แบบเดรัจฉานแบบพื้นฐานคือลองใช้การแบ่งตัวเลขที่กำหนดออกเป็นสองชุดรวมกันเพื่อดูว่าชุดคู่ใดมีผลรวมเท่ากันหรือไม่

สมมติว่า S แทนผลรวมของตัวเลขที่กำหนดทั้งหมด ดังนั้นชุดย่อยที่เท่ากันทั้งสองชุดจะต้องมีผลรวมเท่ากับ S/2 สิ่งนี้จะเปลี่ยนปัญหาของเราเป็น: 'ค้นหาเซตย่อยของตัวเลขที่กำหนดซึ่งมีผลรวมเป็น S/2'

การเขียนโปรแกรมแบบไดนามิกจากล่างขึ้นบน

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

ดังนั้น สำหรับแต่ละตัวเลขที่ดัชนี 'i' (0 ‹= i ‹ num.length) และผลรวม 's' (0 ‹= s ‹= S/2) เรามีสองทางเลือก:

  1. ไม่รวมหมายเลข ในกรณีนี้ เราจะดูว่าเราสามารถรับ 's' จากเซตย่อยได้หรือไม่ โดยไม่รวมตัวเลขนี้: dp[i-1][s]
  2. รวมตัวเลขหากค่าของมันไม่เกิน '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) เรามีสองทางเลือก:

  1. ไม่รวมหมายเลข ในกรณีนี้ เราจะดูว่าเราสามารถหาผลรวม 's' จากเซตย่อยโดยไม่รวมตัวเลขนี้ =› dp[index-1][s]
  2. รวมตัวเลขหากค่าของมันไม่เกิน '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) เรามีสองทางเลือก:

  1. ไม่รวมหมายเลข ในกรณีนี้ เราจะดูว่าเราสามารถหาผลรวม 's' จากเซตย่อยโดยไม่รวมตัวเลขนี้ =› dp[index-1][s]
  2. รวมตัวเลขหากค่าของมันไม่เกิน 's' ในกรณีนี้ เราจะดูว่าเราสามารถหาเซตย่อยเพื่อรับผลรวมที่เหลือได้หรือไม่ =› dp[index-1][s-num[index]]

หากสถานการณ์ใดสถานการณ์หนึ่งข้างต้นเป็นจริง เราสามารถค้นหาเซตย่อยที่มีผลรวมเท่ากับ 's' เราควรเจาะลึกเรื่องนี้ก่อนจึงจะสามารถเรียนรู้วิธีหาเซตย่อยที่ใกล้เคียงที่สุดได้

จำนวนผลรวมย่อย

เมื่อกำหนดชุดของจำนวนบวก ให้ค้นหาจำนวนชุดย่อยทั้งหมดซึ่งผลรวมเท่ากับจำนวน 'S' ที่ระบุ

จากบนลงล่าง

จากล่างขึ้นบน

เราจะพยายามค้นหาว่าเราสามารถสร้างผลรวมที่เป็นไปได้ทั้งหมดกับทุกเซ็ตย่อยเพื่อเติมอาร์เรย์ db[TotalNumbers][S+1] หรือไม่

ดังนั้น ในทุกขั้นตอน เรามีสองทางเลือก:

  1. ไม่รวมหมายเลข นับชุดย่อยทั้งหมดที่ไม่มีหมายเลขที่กำหนดจนถึงผลรวมที่กำหนด =› dp[index-1][sum]
  2. รวมตัวเลขหากค่าของมันไม่เกิน 'ผลรวม' ในกรณีนี้ เราจะนับเซตย่อยทั้งหมดเพื่อให้ได้ผลรวมที่เหลือ =› 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