โปรแกรมที่จะใช้ปัญหาเป้เศษส่วนใน Python

สมมติว่าเรามีสองรายการ น้ำหนักและค่าที่มีความยาวเท่ากันและความจุของค่าอื่น น้ำหนัก[i] และค่า[i] แสดงถึงน้ำหนักและมูลค่าขององค์ประกอบ ith ดังนั้น หากเรารับน้ำหนักที่จุได้มากที่สุด และเราสามารถนำเศษส่วนของน้ำหนักของรายการด้วยค่าตามสัดส่วนได้ เราต้องหาจำนวนมูลค่าสูงสุดที่เราจะได้รับ (ปัดเศษลงเป็นจำนวนเต็มที่ใกล้เคียงที่สุด)

ดังนั้น หากอินพุตมีค่าเท่ากับน้ำหนัก =[6, 7, 3] ค่า =[110, 120, 2] ความจุ =10 เอาต์พุตจะเป็น 178

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• res :=0

  • ทำรายการคู่ P ด้วยน้ำหนักและค่า และจัดเรียงตามค่าต่อน้ำหนัก

  • สำหรับแต่ละคู่ใน P ทำ

    • ความจุ cif คือ 0 แล้ว

      • ออกจากวง

    • ถ้าคู่[0]> ความจุ แล้ว

      • res :=res + ผลหารของ (pair[1] /(pair[0] / capacity)

      • ความจุ :=0

    • มิฉะนั้นเมื่อจับคู่[0] <=ความจุ จากนั้น

      • res :=res + คู่[1]

      • ความจุ :=ความจุ - คู่[0]

  • ส่งคืนค่าพื้นของความละเอียด

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, weights, values, capacity):
      res = 0
      for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]):
         if not bool(capacity):
            break
         if pair[0] > capacity:
            res += int(pair[1] / (pair[0] / capacity))
            capacity = 0
         elif pair[0] <= capacity:
            res += pair[1]
            capacity -= pair[0]
      return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))

อินพุต

[6, 7, 3],[110, 120, 2],10

ผลลัพธ์

230