Fractional knapsack
n आइटम (प्रत्येक का एक भार और एक मान) दिए गए हैं। हम इन्हें एक ऐसे बैग में रखना चाहते हैं, जिसकी क्षमता W है, ताकि बैग का कुल मान अधिकतम हो जाए। इसमें आपको पूरे आइटम के बजाय उसका कोई हिस्सा (fraction) लेने की सुविधा है। यदि आप किसी आइटम का आंशिक हिस्सा लेते हैं, तो उसके मूल्य की गणना उस अंश के अनुपात में की जाती है।इस परिस्थिति में, बैग का अधिकतम कुल मान कितना हो सकता है?
इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n (1 ≤ n ≤ ) और W (1 ≤ W ≤ ) होते हैं, जहाँ n आइटम्स की संख्या है और W बैग की क्षमता दर्शाता है।इसके बाद
n पंक्तियाँ आती हैं, जिनमें प्रत्येक पंक्ति में दो पूर्णांक (1 ≤ , ≤ ) दिए गए हैं, जो आइटम का भार और उसका मूल्य दर्शाते हैं।आउटपुट
कार्यक्रम को बैग में रखे जाने वाले आइटम्स (या उनके हिस्सों) से प्राप्त अधिकतम कुल मान प्रिंट करना चाहिए।
उदाहरण
इनपुट | आउटपुट |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
स्पष्टीकरण
- 60 + 100 + (2/3)120 = 240
- 280 + 100 + (10/20)120 = 440
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB