DAA - กระเป๋าเป้เศษส่วน

อัลกอริทึม Greedy สามารถเข้าใจได้เป็นอย่างดีกับปัญหาที่รู้จักกันดีซึ่งเรียกว่าปัญหาเป้ แม้ว่าปัญหาเดียวกันนี้สามารถแก้ไขได้โดยใช้วิธีการอัลกอริธึมอื่น ๆ แต่วิธีการ Greedy สามารถแก้ปัญหา Fractional Knapsack ได้อย่างสมเหตุสมผลในเวลาที่เหมาะสม ให้เราพูดคุยเกี่ยวกับปัญหาของเป้โดยละเอียด

ปัญหากระเป๋าเป้

กำหนดชุดของรายการแต่ละรายการที่มีน้ำหนักและค่ากำหนดชุดย่อยของรายการที่จะรวมไว้ในคอลเล็กชันเพื่อให้น้ำหนักรวมน้อยกว่าหรือเท่ากับขีด จำกัด ที่กำหนดและมูลค่ารวมจะมากที่สุด

ปัญหากระเป๋าเป้อยู่ในปัญหาการเพิ่มประสิทธิภาพคอมบิเนเตอร์ ปรากฏเป็นปัญหาย่อยในแบบจำลองทางคณิตศาสตร์ที่ซับซ้อนมากขึ้นของปัญหาในโลกแห่งความเป็นจริง แนวทางทั่วไปวิธีหนึ่งในการแก้ปัญหาที่ยากคือการระบุข้อ จำกัด ที่เข้มงวดที่สุดเพิกเฉยต่อปัญหาอื่น ๆ แก้ปัญหากระเป๋าเป้และปรับวิธีแก้ปัญหาเพื่อตอบสนองข้อ จำกัด ที่ถูกเพิกเฉย

การใช้งาน

ในหลาย ๆ กรณีของการจัดสรรทรัพยากรพร้อมกับข้อ จำกัด บางประการปัญหาอาจได้รับในลักษณะเดียวกันของปัญหาเป้ ต่อไปนี้เป็นชุดตัวอย่าง

หาวิธีตัดวัตถุดิบที่สิ้นเปลืองน้อยที่สุด
การเพิ่มประสิทธิภาพพอร์ตโฟลิโอ
ตัดปัญหาสต๊อก

สถานการณ์ปัญหา

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

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

ขึ้นอยู่กับลักษณะของรายการปัญหาของกระเป๋าเป้สะพายหลังแบ่งออกเป็น

กระเป๋าเป้เศษส่วน
Knapsack

กระเป๋าเป้เศษส่วน

ในกรณีนี้ไอเท็มสามารถแบ่งออกเป็นชิ้นเล็ก ๆ ได้ดังนั้นขโมยจึงสามารถเลือกเศษส่วนของไอเท็มได้

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

มี n รายการในร้านค้า
น้ำหนักของ i^th รายการ $ w_ {i}> 0 $
กำไรสำหรับ i^th รายการ $ p_ {i}> 0 $ และ
ความจุของเป้คือ W

ในปัญหาของ Knapsack เวอร์ชันนี้สามารถแบ่งสิ่งของให้เป็นชิ้นเล็กลงได้ ดังนั้นขโมยอาจใช้เวลาเพียงเศษเสี้ยวx_i ของ i^th สิ่งของ.

$$ 0 \ leqslant x_ {i} \ leqslant 1 $$

i^th รายการคิดเป็นน้ำหนัก $ x_ {i} .w_ {i} $ กับน้ำหนักรวมในกระเป๋าเป้และกำไร $ x_ {i} .p_ {i} $ จากกำไรทั้งหมด

ดังนั้นวัตถุประสงค์ของอัลกอริทึมนี้คือเพื่อ

$$ maximize \: \ displaystyle \ sum \ LIMIT_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

ขึ้นอยู่กับข้อ จำกัด

$$ \ displaystyle \ sum \ LIMIT_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

เป็นที่ชัดเจนว่าทางออกที่ดีที่สุดจะต้องเติมเป้ให้พอดีมิฉะนั้นเราสามารถเพิ่มเศษหนึ่งส่วนของรายการที่เหลือและเพิ่มผลกำไรโดยรวมได้

ดังนั้นวิธีการแก้ปัญหาที่ดีที่สุดสามารถหาได้จาก

$$ \ displaystyle \ sum \ LIMIT_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

ในบริบทนี้อันดับแรกเราต้องจัดเรียงรายการเหล่านั้นตามค่าของ $ \ frac {p_ {i}} {w_ {i}} $ ดังนั้น $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $ ที่นี่x เป็นอาร์เรย์สำหรับเก็บเศษของรายการ

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

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

หากรายการที่ให้มาถูกจัดเรียงเป็นลำดับที่ลดลง $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $ แล้ว whileloop จะใช้เวลาใน O(n); ดังนั้นเวลาทั้งหมดรวมถึงการจัดเรียงจึงอยู่ในO(n logn).

ตัวอย่าง

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

สิ่งของ	ก	ข	ค	ง
กำไร	280	100	120	120
น้ำหนัก	40	10	20	24
อัตราส่วน $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

เนื่องจากรายการที่ให้มาไม่ได้จัดเรียงตาม $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $ หลังจากจัดเรียงรายการจะเป็นดังที่แสดงในตารางต่อไปนี้

สิ่งของ	ข	ก	ค	ง
กำไร	100	280	120	120
น้ำหนัก	10	40	20	24
อัตราส่วน $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

วิธีการแก้

หลังจากจัดเรียงรายการทั้งหมดตาม $ \ frac {p_ {i}} {w_ {i}} $ ก่อนอื่นB ถูกเลือกให้เป็นน้ำหนักของ Bน้อยกว่าความจุของเป้ ถัดไปรายการA ถูกเลือกเนื่องจากความจุที่มีอยู่ของกระเป๋าเป้มีค่ามากกว่าน้ำหนักของ A. ตอนนี้Cได้รับเลือกให้เป็นรายการถัดไป อย่างไรก็ตามไม่สามารถเลือกรายการทั้งหมดได้เนื่องจากความจุที่เหลือของกระเป๋าเป้มีค่าน้อยกว่าน้ำหนักของC.

ดังนั้นเศษส่วนของ C (เช่น (60 - 50) / 20) ถูกเลือก

ตอนนี้ความจุของเป้เท่ากับรายการที่เลือก ดังนั้นจึงไม่สามารถเลือกรายการได้อีก

น้ำหนักรวมของรายการที่เลือกคือ 10 + 40 + 20 * (10/20) = 60

และกำไรรวมคือ 100 + 280 + 120 * (10/20) = 380 + 60 = 440

นี่คือทางออกที่ดีที่สุด เราไม่สามารถทำกำไรได้มากขึ้นหากเลือกชุดค่าผสมต่างๆ