DAA - 0-1 เป้

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

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

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

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

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

ตัวอย่าง -1

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

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

โดยไม่ได้คำนึงถึงกำไรต่อหน่วยน้ำหนัก (pi/wi) หากเราใช้วิธีโลภในการแก้ปัญหานี้ข้อแรก 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 สิ่งของและน้ำหนักของ ith รายการคือ wi และกำไรจากการเลือกรายการนี้คือ pi. ขโมยควรเอาของอะไร?

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

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

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

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

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

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

  • ทั้งสองลำดับ v = <v1, v2, …, vn> และ w = <w1, w2, …, wn>

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)