C++ में फ्रैक्शनल नैपसेक समस्या एक बैग को दिए गए वजन और लाभ की वस्तुओं से इस तरह भरने के तरीके की पहचान करने से संबंधित है कि बैग में अधिकतम सीमा से अधिक हुए बिना अधिकतम मूल्य हो।
C++ में फ्रैक्शनल नैपसैक समस्या को कैसे हल करें
वस्तुओं के एक सेट को देखते हुए, प्रत्येक दिए गए वजन और लाभ के साथ, वस्तुओं की प्रत्येक संख्या को इस तरह से निर्धारित करें कि वस्तुओं का कुल वजन बैग की अधिकतम सीमा से कम हो, लेकिन मूल्य जितना संभव हो उतना बड़ा रखा जाना चाहिए।
फ्रैक्शनल नैपसैक समस्या को लागू करने के लिए एल्गोरिदम
नैपसैक एल्गोरिथम की कार्यप्रणाली को निम्नलिखित बिंदुओं के माध्यम से समझा जा सकता है:
- वजन और लाभ के दो सरणियाँ लें।
- अधिकतम बोरी मूल्य को W पर सेट करें।
- दोनों मापदंडों का अनुपात लेकर घनत्व निर्धारित करें।
- वस्तुओं को घनत्व के घटते क्रम में क्रमबद्ध करें।
- मान तब तक जोड़ें जब तक यह <=W न हो जाए।
फ्रैक्शनल नैपसेक समस्या को हल करने का लालची दृष्टिकोण
लालची दृष्टिकोण का लक्ष्य प्रत्येक चरण में आदर्श विकल्प चुनना है, जिससे अंत में आदर्श समाधान प्राप्त होता है। यह समस्याओं को चरण दर चरण हल करता है और निष्कर्ष तक ले जाता है न कि केवल अंत में निष्कर्ष निकालता है। यह C++ में फ्रैक्शनल नैपसैक समस्या के समाधान को लागू करने के लिए एक स्रोत कोड है:
#शामिल है
का उपयोग करते हुए नाम स्थान कक्षा ;
struct वस्तु {
int यहाँ मूल्य, वजन ;
वस्तु ( int यहाँ कीमत, int यहाँ वज़न )
: कीमत ( कीमत ) , वज़न ( वज़न )
{
}
} ;
बूल सीएमपी ( struct वस्तु एक्स, struct वस्तु वाई )
{
दोहरा ए 1 = ( दोहरा ) एक्स। कीमत / एक्स। वज़न ;
दोहरा ए2 = ( दोहरा ) और। कीमत / और। वज़न ;
वापस करना ए 1 > ए2 ;
}
दोहरा फ्रैक्शनल नैपसैक ( struct वस्तु गिरफ्तार [ ] ,
int यहाँ में, int यहाँ आकार )
{
क्रम से लगाना ( एआर, एआर + आकार, सीएमपी ) ;
int यहाँ वक्रवजन = 0 ;
दोहरा अंतिम मूल्य = 0.0 ;
के लिए ( int यहाँ मैं = 0 ; मैं < आकार ; मैं ++ ) {
अगर ( वक्रवजन + आगमन [ मैं ] . वज़न <= में ) {
वक्रवजन + = आगमन [ मैं ] . वज़न ;
अंतिम मूल्य + = आगमन [ मैं ] . कीमत ;
}
अन्य {
int यहाँ अवशेष = में - वक्रवजन ;
अंतिम मूल्य + = आगमन [ मैं ] . कीमत
* ( ( दोहरा ) अवशेष
/ आगमन [ मैं ] . वज़न ) ;
तोड़ना ;
}
}
वापस करना अंतिम मूल्य ;
}
int यहाँ में = 60 ;
वस्तु गिरफ्तार [ ] = { { 100 , बीस } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int यहाँ आकार = का आकार ( आगमन ) / का आकार ( आगमन [ 0 ] ) ;
अदालत << 'अधिकतम लाभ = '
<< फ्रैक्शनल नैपसैक ( एआर, वी, आकार ) ;
वापस करना 0 ;
}
इस कोड में, एक वस्तु संरचना को परिभाषित किया जाता है जिसमें वजन और लाभ मूल्य संग्रहीत होते हैं। बूल सीएमपी() का उपयोग दो वस्तुओं के वजन और मूल्य के अनुपात के आधार पर दो वस्तुओं के बीच तुलना करने के लिए किया जाता है। सरणी को अवरोही क्रम में व्यवस्थित किया जाता है और मूल्य तब तक जुड़ता रहता है जब तक यह अधिकतम तक नहीं पहुंच जाता। यदि वर्तमान मूल्य अनुमेय है और सीमा के भीतर है, तो इसे जोड़ा जाता है, अन्यथा इसका घटा हुआ अनुपात बैग में जोड़ा जाता है। वजन और मूल्य का परिमाण मुख्य कोड में इनपुट होता है और अधिकतम लाभ आउटपुट पर मुद्रित होता है।
स्नैक में संग्रहीत अधिकतम लाभ 580 है।
निष्कर्ष
C++ में फ्रैक्शनल नैपसेक समस्या एक बैग को दिए गए वजन और लाभ की वस्तुओं से इस तरह भरने के तरीके की पहचान करने से संबंधित है कि बैग में अधिकतम सीमा से अधिक हुए बिना अधिकतम मूल्य हो। इसे लालची दृष्टिकोण द्वारा प्राप्त किया जा सकता है जिसका उद्देश्य प्रत्येक चरण में आदर्श विकल्प चुनना है, जिससे अंत में आदर्श समाधान प्राप्त होता है।