C++లోని ఫ్రాక్షనల్ నాప్‌సాక్ సమస్య అనేది బ్యాగ్ గరిష్ట పరిమితిని మించకుండా గరిష్ట విలువను కలిగి ఉండే విధంగా ఇచ్చిన బరువు మరియు లాభంతో కూడిన వస్తువులతో బ్యాగ్‌ని నింపే మార్గాన్ని గుర్తించడాన్ని సూచిస్తుంది.
C++లో ఫ్రాక్షనల్ నాప్‌సాక్ సమస్యను ఎలా పరిష్కరించాలి
వస్తువుల సమితిని బట్టి, ప్రతి ఒక్కటి ఇచ్చిన బరువు మరియు లాభంతో, వస్తువుల మొత్తం బరువు బ్యాగ్ యొక్క గరిష్ట పరిమితి కంటే తక్కువగా ఉండేలా, అటువంటి కలయికలో ప్రతి వస్తువుల సంఖ్యను నిర్ణయించండి, అయితే విలువ వీలైనంత పెద్దదిగా ఉండాలి.
ఫ్రాక్షనల్ నాప్‌సాక్ సమస్యను అమలు చేయడానికి అల్గోరిథం
నాప్‌సాక్ అల్గోరిథం పనితీరును ఈ క్రింది అంశాల ద్వారా అర్థం చేసుకోవచ్చు:
- బరువు మరియు లాభం యొక్క రెండు శ్రేణులను తీసుకోండి.
- గరిష్ట సాక్ విలువను Wకి సెట్ చేయండి.
- రెండు పారామితుల నిష్పత్తిని తీసుకోవడం ద్వారా సాంద్రతను నిర్ణయించండి.
- సాంద్రత తగ్గే క్రమంలో అంశాలను క్రమబద్ధీకరించండి.
- <=W వరకు విలువలను జోడించండి.
ఫ్రాక్షనల్ నాప్‌సాక్ సమస్యను పరిష్కరించడానికి అత్యాశ అప్రోచ్
అత్యాశ విధానం ప్రతి దశలో ఆదర్శవంతమైన ఎంపికలను లక్ష్యంగా చేసుకుంటుంది, చివరికి ఆదర్శవంతమైన పరిష్కారానికి దారి తీస్తుంది. ఇది సమస్యలను దశల వారీగా పరిష్కరిస్తుంది, చివరికి ఫలితాలను మాత్రమే ముగించే బదులు ముగింపులకు దారి తీస్తుంది. ఇది C++లో పాక్షిక నాప్‌సాక్ సమస్యకు పరిష్కారాన్ని అమలు చేయడానికి సోర్స్ కోడ్:
#
ఉపయోగించి నేమ్‌స్పేస్ std ;
నిర్మాణం వస్తువు {
int విలువ, బరువు ;
వస్తువు ( int విలువ, int బరువు )
: విలువ ( విలువ ) , బరువు ( బరువు )
{
}
} ;
బూల్ సెం.మీ ( నిర్మాణం వస్తువు x, నిర్మాణం ఆబ్జెక్ట్ y )
{
రెట్టింపు A1 = ( రెట్టింపు ) x. విలువ / x. బరువు ;
రెట్టింపు A2 = ( రెట్టింపు ) మరియు. విలువ / మరియు. బరువు ;
తిరిగి A1 > A2 ;
}
రెట్టింపు భిన్నమైన నాప్‌సాక్ ( నిర్మాణం ఆబ్జెక్ట్ అర్ [ ] ,
int IN, int పరిమాణం )
{
క్రమబద్ధీకరించు ( అర్, అర్ర్ + పరిమాణం, సెం.మీ ) ;
int కర్ర బరువు = 0 ;
రెట్టింపు తుది విలువ = 0.0 ;
కోసం ( int i = 0 ; i < పరిమాణం ; i ++ ) {
ఉంటే ( కర్ర బరువు + అరె [ i ] . బరువు <= IN ) {
కర్ర బరువు + = అరె [ i ] . బరువు ;
తుది విలువ + = అరె [ i ] . విలువ ;
}
లేకపోతే {
int మిగిలి ఉన్నాయి = IN - కర్ర బరువు ;
తుది విలువ + = అరె [ i ] . విలువ
* ( ( రెట్టింపు ) మిగిలి ఉన్నాయి
/ అరె [ i ] . బరువు ) ;
బ్రేక్ ;
}
}
తిరిగి తుది విలువ ;
}
int లో = 60 ;
ఆబ్జెక్ట్ అర్ [ ] = { { 100 , ఇరవై } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int పరిమాణం = పరిమాణం ( అరె ) / పరిమాణం ( అరె [ 0 ] ) ;
కోట్ << 'గరిష్ట లాభం ='
<< భిన్నమైన నాప్‌సాక్ ( arr, v, పరిమాణం ) ;
తిరిగి 0 ;
}
ఈ కోడ్‌లో, ఒక వస్తువు నిర్మాణం నిర్వచించబడింది, దానిలో నిల్వ చేయబడిన బరువు మరియు లాభ విలువలు ఉంటాయి. రెండు వస్తువుల బరువు మరియు విలువ నిష్పత్తి ఆధారంగా రెండు వస్తువుల మధ్య పోలిక చేయడానికి bool cmp() ఉపయోగించబడుతుంది. శ్రేణి అవరోహణ క్రమంలో అమర్చబడింది మరియు గరిష్ట స్థాయికి చేరుకునే వరకు విలువ జోడిస్తూనే ఉంటుంది. ప్రస్తుత విలువ అనుమతించదగినది మరియు పరిమితి లోపల ఉంటే, అది జోడించబడుతుంది, లేకుంటే దాని తగ్గిన నిష్పత్తి బ్యాగ్‌కి జోడించబడుతుంది. బరువు మరియు విలువ యొక్క పరిమాణం ప్రధాన కోడ్‌లో ఇన్‌పుట్ చేయబడుతుంది మరియు గరిష్ట లాభం అవుట్‌పుట్‌పై ముద్రించబడుతుంది.
చిరుతిండిలో నిల్వ చేయబడిన గరిష్ట లాభం 580.
ముగింపు
C++లోని ఫ్రాక్షనల్ నాప్‌సాక్ సమస్య అనేది బ్యాగ్ గరిష్ట పరిమితిని మించకుండా గరిష్ట విలువను కలిగి ఉండే విధంగా ఇచ్చిన బరువు మరియు లాభంతో కూడిన వస్తువులతో బ్యాగ్‌ని నింపే మార్గాన్ని గుర్తించడాన్ని సూచిస్తుంది. ప్రతి దశలోనూ ఆదర్శవంతమైన ఎంపికలను లక్ష్యంగా చేసుకుని, చివరికి ఆదర్శవంతమైన పరిష్కారానికి దారితీసే అత్యాశతో కూడిన విధానం ద్వారా దీనిని సాధించవచ్చు.