C++ میں فریکشنل نیپ سیک کے مسئلے سے مراد دیے گئے وزن اور منافع کی اشیاء سے بیگ کو بھرنے کے طریقے کی نشاندہی کرنا ہے کہ بیگ میں زیادہ سے زیادہ حد سے تجاوز کیے بغیر زیادہ سے زیادہ قیمت موجود ہو۔
C++ میں فریکشنل نیپ سیک کا مسئلہ کیسے حل کریں۔
اشیاء کے ایک سیٹ کو دیکھتے ہوئے، ہر ایک دیئے گئے وزن اور منافع کے ساتھ، ہر ایک اشیاء کی تعداد کو اس طرح سے متعین کریں کہ اشیاء کا کل وزن تھیلی کی زیادہ سے زیادہ حد سے کم ہو، لیکن قیمت کو ہر ممکن حد تک بڑا رکھنا چاہیے۔
فریکشنل نیپ سیک کے مسئلے کو نافذ کرنے کے لیے الگورتھم
Knapsack الگورتھم کے کام کو درج ذیل نکات کے ذریعے سمجھا جا سکتا ہے۔
- وزن اور منافع کی دو صفیں لیں۔
- زیادہ سے زیادہ بوری کی قیمت W پر سیٹ کریں۔
- دونوں پیرامیٹرز کے تناسب کو لے کر کثافت کا تعین کریں۔
- آئٹمز کو کثافت کے کم ہوتے ہوئے ترتیب دیں۔
- اقدار کو اس وقت تک شامل کریں جب تک کہ یہ <=W نہ ہو۔
فریکشنل نیپ سیک کے مسئلے کو حل کرنے کے لیے لالچی نقطہ نظر
لالچی نقطہ نظر کا مقصد ہر قدم پر مثالی انتخاب کرنا ہے، جو آخر میں مثالی حل کی طرف لے جاتا ہے۔ یہ مسائل کو مرحلہ وار حل کرتا ہے جس کے نتیجے میں نتائج اخذ کرنے کے بجائے نتائج پر پہنچتے ہیں۔ یہ C++ میں فریکشنل نیپ سیک مسئلے کے حل کو نافذ کرنے کے لیے ایک سورس کوڈ ہے:
#include
استعمال کرتے ہوئے نام کی جگہ std ;
ساخت چیز {
int قدر، وزن ;
چیز ( int قدر، int وزن )
: قدر ( قدر ) ، وزن ( وزن )
{
}
} ;
bool cmp ( ساخت آبجیکٹ ایکس، ساخت اعتراض y )
{
دگنا A1 = ( دگنا ) ایکس. قدر / ایکس. وزن ;
دگنا A2 = ( دگنا ) اور قدر / اور وزن ;
واپسی A1 > A2 ;
}
دگنا fractional Knapsack ( ساخت اعتراض arr [ ] ،
int میں، int سائز )
{
ترتیب دیں ( arr، arr + سائز، cmp ) ;
int کم وزن = 0 ;
دگنا حتمی قدر = 0.0 ;
کے لیے ( int میں = 0 ; میں < سائز ; میں ++ ) {
اگر ( کم وزن + arr [ میں ] . وزن <= میں ) {
کم وزن + = arr [ میں ] . وزن ;
حتمی قدر + = arr [ میں ] . قدر ;
}
اور {
int باقی = میں - کم وزن ;
حتمی قدر + = arr [ میں ] . قدر
* ( ( دگنا ) باقی
/ arr [ میں ] . وزن ) ;
توڑنا ;
}
}
واپسی حتمی قدر ;
}
int میں = 60 ;
اعتراض arr [ ] = { { 100 ، بیس } ،
{ 380 ، 40 } ،
{ 140 ، 10 } ،
{ 180 ، 30 } } ;
int سائز = کا سائز ( arr ) / کا سائز ( arr [ 0 ] ) ;
cout << 'زیادہ سے زیادہ منافع ='
<< fractional Knapsack ( arr، v، سائز ) ;
واپسی 0 ;
}
اس کوڈ میں، ایک آبجیکٹ کی ساخت کی وضاحت کی گئی ہے جس میں وزن اور منافع کی قدریں محفوظ ہیں۔ bool cmp() دو اشیاء کے وزن اور قیمت کے تناسب کی بنیاد پر دو اشیاء کے درمیان موازنہ کرنے کے لیے استعمال ہوتا ہے۔ صف کو نزولی ترتیب میں ترتیب دیا گیا ہے اور قیمت اس وقت تک بڑھتی رہتی ہے جب تک کہ یہ زیادہ سے زیادہ نہ پہنچ جائے۔ اگر موجودہ قیمت جائز ہے اور حد کے اندر ہے تو اسے شامل کر دیا جائے گا، ورنہ اس کا گھٹا ہوا تناسب بیگ میں شامل کر دیا جائے گا۔ وزن اور قدر کی شدت مین کوڈ میں ان پٹ ہوتی ہے اور زیادہ سے زیادہ منافع آؤٹ پٹ پر پرنٹ کیا جاتا ہے۔
زیادہ سے زیادہ منافع جو اسنیک میں ذخیرہ کیا گیا تھا 580 ہے۔
نتیجہ
C++ میں فریکشنل نیپ سیک کے مسئلے سے مراد دیے گئے وزن اور منافع کی اشیاء سے بیگ کو بھرنے کے طریقے کی نشاندہی کرنا ہے کہ بیگ میں زیادہ سے زیادہ حد سے تجاوز کیے بغیر زیادہ سے زیادہ قیمت موجود ہو۔ یہ لالچی نقطہ نظر سے حاصل کیا جا سکتا ہے جس کا مقصد ہر قدم پر مثالی انتخاب کرنا ہے، جس کے نتیجے میں آخر میں مثالی حل نکلتا ہے۔