0-1 बैकपैक: न्यूनतम आइटम
Problem
दिया गया N द्रव्यमान m1, …, mN के आइटम। वे एक बैकपैक भरते हैं जो M से अधिक वजन का सामना नहीं कर सकता है। यथासंभव कम से कम वस्तुओं का उपयोग करके ठीक M में वजन कैसे बढ़ाया जाए?
इनपुट:
- पहली पंक्ति में प्राकृतिक संख्या N 100 से अधिक नहीं और प्राकृतिक संख्या M 10000 से अधिक नहीं होती है;
- दूसरी पंक्ति में N प्राकृत संख्या mi 100 से अधिक नहीं है।
आउटपुट: यदि आप दिए गए वजन तक नहीं पहुंच सकते हैं तो आपको जितने आइटम की आवश्यकता है, या 0 प्रिंट करें।
उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
1 5968
18
0 |