एल्गोरिदम और डेटा संरचनाएँ

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

स्पष्टीकरण

  1. 60 + 100 + (2/3)120 = 240

  2. 280 + 100 + (10/20)120 = 440

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue