Greedy एल्गोरिदम
Greedy एल्गोरिदम ऐसे लोकप्रिय तरीक़ों का समूह हैं, जो अंतिम हल को चरण दर चरण निर्मित करते हैं और हर कदम पर सबसे स्पष्ट/उत्तम विकल्प चुनते हैं। ये आमतौर पर काफी सरल होते हैं, लेकिन कभी-कभी हर चरण में सही हीयूरिस्टिक (heuristic) समझना चुनौतीपूर्ण हो सकता है।
चुनौती
आपके पास एक knapsack और
n आइटम्स हैं। आप इनमें से जितने हो सके उतने आइटम्स रखना चाहते हैं, लेकिन आपको पता है कि अगर आइटम्स का कुल वज़न t से ज़्यादा होगा तो knapsack फट सकता है। आप जानना चाहते हैं कि अधिकतम कितने आइटम्स अपने बैग में रखे जा सकते हैं ताकि उसे आसानी से उठाया जा सके।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n (1 ≤ n ≤ ) और t (1 ≤ t ≤ ) दिए होते हैं — ये क्रमशः आइटम्स की संख्या और knapsack की अधिकतम वहन क्षमता को दर्शाते हैं।अगली पंक्ति में
n स्पेस से अलग किए गए (1 ≤ ≤ ) वज़न दिए होते हैं, जो कि प्रत्येक आइटम का वज़न बताते हैं।आउटपुट
प्रोग्राम को अधिकतम उन आइटम्स की संख्या प्रिंट करनी चाहिए जिन्हें आप उठा सकते हैं।
उदाहरण
इनपुट | आउटपुट |
7 10
4 1 2 5 8 7 1 | 4 |
व्याख्या
हम
1, 2, 5, 1 या 4, 1, 2, 1 या 1, 2, 7, 1 उठा सकते हैं। इन सभी स्थितियों में कुल 4 आइटम्स लिए गए हैं।Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB