C++ இல் பகுதியளவு நாப்சாக் சிக்கலை எவ்வாறு தீர்ப்பது

C++ இல் உள்ள fractional knapsack சிக்கல் என்பது, கொடுக்கப்பட்ட எடை மற்றும் லாபம் உள்ள பொருட்களைக் கொண்டு பையை நிரப்புவதற்கான வழியை அடையாளம் காண்பதைக் குறிக்கிறது, அதாவது பை அதிகபட்ச வரம்பை மீறாமல் அதிகபட்ச மதிப்பைக் கொண்டிருக்கும்.

C++ இல் பகுதியளவு நாப்சாக் சிக்கலை எவ்வாறு தீர்ப்பது

கொடுக்கப்பட்ட எடை மற்றும் லாபத்துடன் கூடிய பொருட்களின் தொகுப்பைக் கொண்டு, பொருட்களின் மொத்த எடை பையின் அதிகபட்ச வரம்பை விட குறைவாக இருக்கும், ஆனால் மதிப்பு முடிந்தவரை பெரியதாக இருக்க வேண்டும்.

பகுதியளவு நாப்சாக் சிக்கலைச் செயல்படுத்துவதற்கான அல்காரிதம்

நாப்சாக் அல்காரிதத்தின் செயல்பாட்டை பின்வரும் புள்ளிகள் மூலம் புரிந்து கொள்ளலாம்:

• எடை மற்றும் லாபத்தின் இரண்டு வரிசைகளை எடுத்துக் கொள்ளுங்கள்.
• அதிகபட்ச சாக் மதிப்பை W ஆக அமைக்கவும்.
• இரண்டு அளவுருக்களின் விகிதத்தை எடுத்து அடர்த்தியை தீர்மானிக்கவும்.
• அடர்த்தி குறையும் வரிசையில் பொருட்களை வரிசைப்படுத்தவும்.
• <=W ஆகும் வரை மதிப்புகளைச் சேர்க்கவும்.

பகுதியளவு நாப்கின் சிக்கலைத் தீர்க்க பேராசை அணுகுமுறை

பேராசை அணுகுமுறை ஒவ்வொரு அடியிலும் சிறந்த தேர்வுகளை செய்வதை நோக்கமாகக் கொண்டுள்ளது, இறுதியில் சிறந்த தீர்வுக்கு வழிவகுக்கும். இது சிக்கல்களை படிப்படியாக தீர்க்கிறது, இறுதியில் முடிவுகளை மட்டுமே முடிப்பதற்கு பதிலாக முடிவுகளுக்கு வழிவகுக்கிறது. இது C++ இல் உள்ள பகுதியளவு நாப்சாக் பிரச்சனைக்கான தீர்வைச் செயல்படுத்துவதற்கான ஒரு மூலக் குறியீடு:

இந்த குறியீட்டில், எடை மற்றும் இலாப மதிப்புகள் சேமிக்கப்படும் ஒரு பொருள் அமைப்பு வரையறுக்கப்படுகிறது. இரண்டு பொருட்களின் எடை மற்றும் மதிப்பின் விகிதத்தின் அடிப்படையில் இரண்டு பொருள்களை ஒப்பிடுவதற்கு bool cmp() பயன்படுகிறது. வரிசை இறங்கு வரிசையில் அமைக்கப்பட்டுள்ளது மற்றும் அதிகபட்சம் அடையும் வரை மதிப்பு கூட்டிக்கொண்டே இருக்கும். தற்போதைய மதிப்பு அனுமதிக்கப்பட்ட மற்றும் வரம்பிற்குள் இருந்தால், அது சேர்க்கப்படும், இல்லையெனில் அதன் குறைக்கப்பட்ட விகிதம் பையில் சேர்க்கப்படும். எடை மற்றும் மதிப்பின் அளவு முக்கிய குறியீட்டில் உள்ளீடு மற்றும் அதிகபட்ச லாபம் வெளியீட்டில் அச்சிடப்படுகிறது.

சிற்றுண்டியில் சேமிக்கப்பட்ட அதிகபட்ச லாபம் 580 ஆகும்.

முடிவுரை

C++ இல் உள்ள fractional knapsack சிக்கல் என்பது, கொடுக்கப்பட்ட எடை மற்றும் லாபம் உள்ள பொருட்களைக் கொண்டு பையை நிரப்புவதற்கான வழியை அடையாளம் காண்பதைக் குறிக்கிறது, அதாவது பை அதிகபட்ச வரம்பை மீறாமல் அதிகபட்ச மதிப்பைக் கொண்டிருக்கும். ஒவ்வொரு அடியிலும் சிறந்த தேர்வுகளை மேற்கொள்வதை நோக்கமாகக் கொண்ட பேராசை அணுகுமுறையால் இதை அடைய முடியும், இறுதியில் சிறந்த தீர்வுக்கு வழிவகுக்கும்.