DAA - 0-1 เป้

ในบทช่วยสอนนี้ก่อนหน้านี้เราได้พูดถึงปัญหา Fractional Knapsack โดยใช้วิธีโลภ เราได้แสดงให้เห็นแล้วว่า Greedy approach เป็นทางออกที่ดีที่สุดสำหรับ Fractional Knapsack อย่างไรก็ตามบทนี้จะกล่าวถึงปัญหาของเป้ 0-1 และการวิเคราะห์

ใน 0-1 กระเป๋าเป้ไม่สามารถแตกหักได้ซึ่งหมายความว่าขโมยควรนำของไปทั้งหมดหรือควรทิ้งไว้ นี่คือเหตุผลที่เรียกมันว่าเป้ 0-1

ดังนั้นในกรณีของ 0-1 Knapsack ค่าของ x_i สามารถเป็นได้ 0 หรือ 1โดยที่ข้อ จำกัด อื่น ๆ ยังคงเหมือนเดิม

0-1 เป้ไม่สามารถแก้ไขได้ด้วยวิธีโลภ วิธีการโลภไม่ได้ช่วยให้มั่นใจได้ว่าจะแก้ปัญหาได้ดี ในหลาย ๆ กรณีวิธีโลภอาจให้ทางออกที่ดีที่สุด

ตัวอย่างต่อไปนี้จะสร้างคำสั่งของเรา

ตัวอย่าง -1

ให้เราพิจารณาว่าความจุของเป้คือ W = 25 และรายการต่างๆดังแสดงในตารางต่อไปนี้

สิ่งของ	ก	ข	ค	ง
กำไร	24	18	18	10
น้ำหนัก	24	10	10	7

โดยไม่ได้คำนึงถึงกำไรต่อหน่วยน้ำหนัก (p_i/w_i) หากเราใช้วิธีโลภในการแก้ปัญหานี้ข้อแรก Aจะได้รับการคัดเลือกให้เป็นก็จะมีส่วนร่วมสูงสุด_ฉันกำไรแม่ในหมู่องค์ประกอบทั้งหมด

หลังจากเลือกรายการ Aจะไม่มีการเลือกรายการเพิ่มเติม ดังนั้นสำหรับชุดของรายการที่กำหนดนี้กำไรทั้งหมดคือ24. ในขณะที่ทางออกที่ดีที่สุดสามารถทำได้โดยการเลือกรายการB และ C โดยที่กำไรรวมคือ 18 + 18 = 36

ตัวอย่าง -2

แทนที่จะเลือกรายการที่อยู่บนพื้นฐานของผลประโยชน์โดยรวมในตัวอย่างนี้รายการที่ได้รับการคัดเลือกขึ้นอยู่กับอัตราส่วนP _ฉัน / _wฉัน ให้เราพิจารณาว่าความจุของกระเป๋าเป้คือW = 60 และรายการดังที่แสดงในตารางต่อไปนี้

สิ่งของ	ก	ข	ค
ราคา	100	280	120
น้ำหนัก	10	40	20
อัตราส่วน	10	7	6

โดยใช้วิธีโลภรายการแรก Aถูกเลือก จากนั้นรายการถัดไปBถูกเลือก ดังนั้นผลกำไรทั้งหมดคือ100 + 280 = 380. อย่างไรก็ตามทางออกที่ดีที่สุดของอินสแตนซ์นี้สามารถทำได้โดยการเลือกรายการB และ Cโดยที่กำไรทั้งหมดคือ 280 + 120 = 400.

ดังนั้นจึงสรุปได้ว่าวิธีโลภอาจไม่ได้ให้ทางออกที่ดีที่สุด

ในการแก้ปัญหา 0-1 Knapsack ต้องใช้วิธี Dynamic Programming

คำชี้แจงปัญหา

โจรจะปล้นร้านและสามารถดำเนินการได้สูงสุด_ฉันน้ำหนัก mal ของWเข้าไปในกระเป๋าเป้ของเขา มีn สิ่งของและน้ำหนักของ i^th รายการคือ w_i และกำไรจากการเลือกรายการนี้คือ p_i. ขโมยควรเอาของอะไร?

วิธีการเขียนโปรแกรมแบบไดนามิก

ปล่อย i เป็นรายการที่มีหมายเลขสูงสุดในโซลูชันที่เหมาะสมที่สุด S สำหรับ Wดอลลาร์. แล้วS^' = S - {i} เป็นทางออกที่ดีที่สุดสำหรับ W - w_i ดอลลาร์และมูลค่าของการแก้ปัญหา S คือ V_i บวกค่าของปัญหาย่อย

เราสามารถแสดงข้อเท็จจริงนี้ในสูตรต่อไปนี้: กำหนด c[i, w] เพื่อเป็นทางออกสำหรับรายการ 1,2, … , iและสูงสุด_ฉันน้ำหนักแม่w.

อัลกอริทึมรับอินพุตต่อไปนี้

• สูงสุด_ฉันน้ำหนักแม่W

• จำนวนรายการ n

• ทั้งสองลำดับ v = <v₁, v₂, …, v_n> และ w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

ชุดรายการที่จะนำไปอนุมานได้จากตารางเริ่มต้นที่ c[n, w] และติดตามย้อนกลับว่าค่าที่เหมาะสมมาจากไหน

ถ้าc [i, w] = c [i-1, w]แล้วรายการi ไม่ได้เป็นส่วนหนึ่งของการแก้ปัญหาและเรายังคงติดตามด้วย c[i-1, w]. มิฉะนั้นรายการi เป็นส่วนหนึ่งของการแก้ปัญหาและเรายังคงติดตามด้วย c[i-1, w-W].

การวิเคราะห์

อัลกอริทึมนี้ใช้เวลาθ ( n , w ) เท่าที่ตารางcมี ( n + 1) รายการ ( w + 1) ซึ่งแต่ละรายการต้องใช้เวลาในการคำนวณθ (1)