C++-এ ভগ্নাংশের ন্যাপস্যাক সমস্যাটি একটি নির্দিষ্ট ওজন এবং লাভের আইটেমগুলি দিয়ে একটি ব্যাগ পূরণ করার একটি উপায় সনাক্ত করাকে বোঝায় যাতে ব্যাগটি সর্বাধিক সীমা অতিক্রম না করে সর্বোচ্চ মান ধারণ করে।
কিভাবে C++ এ ভগ্নাংশ ন্যাপস্যাক সমস্যা সমাধান করবেন
প্রদত্ত ওজন এবং লাভ সহ আইটেমগুলির একটি সেট দেওয়া, প্রতিটি আইটেমের সংখ্যা এমনভাবে নির্ধারণ করুন যাতে আইটেমগুলির মোট ওজন ব্যাগের সর্বোচ্চ সীমার চেয়ে কম হয়, তবে মানটি যতটা সম্ভব বড় রাখতে হবে।
ভগ্নাংশ ন্যাপস্যাক সমস্যা বাস্তবায়নের জন্য অ্যালগরিদম
ন্যাপস্যাক অ্যালগরিদমের কার্যকারিতা নিম্নলিখিত বিষয়গুলির মাধ্যমে বোঝা যায়:
- ওজন এবং লাভের দুটি অ্যারে নিন।
- সর্বোচ্চ বস্তা মান W এ সেট করুন।
- উভয় প্যারামিটারের অনুপাত গ্রহণ করে ঘনত্ব নির্ণয় কর।
- ঘনত্বের ক্রমানুসারে আইটেম সাজান।
- <=W না হওয়া পর্যন্ত মান যোগ করুন।
ভগ্নাংশ ন্যাপস্যাক সমস্যা সমাধানের লোভী দৃষ্টিভঙ্গি
লোভী পদ্ধতির লক্ষ্য প্রতিটি ধাপে আদর্শ পছন্দ করা, যা শেষে আদর্শ সমাধানের দিকে নিয়ে যায়। এটি ধাপে ধাপে সমস্যার সমাধান করে এবং ফলাফলগুলি শেষ পর্যন্ত উপসংহার না করে সিদ্ধান্তে পৌঁছায়। এটি C++ এ ভগ্নাংশের ন্যাপস্যাক সমস্যার সমাধান বাস্তবায়নের জন্য একটি উৎস কোড:
#include
ব্যবহার নামস্থান std ;
গঠন অবজেক্ট {
int মান, ওজন ;
অবজেক্ট ( int মূল্য int ওজন )
: মান ( মান ) , ওজন ( ওজন )
{
}
} ;
bool cmp ( গঠন বস্তু x, গঠন অবজেক্ট y )
{
দ্বিগুণ A1 = ( দ্বিগুণ ) এক্স. মান / এক্স. ওজন ;
দ্বিগুণ A2 = ( দ্বিগুণ ) এবং. মান / এবং. ওজন ;
ফিরে A1 > A2 ;
}
দ্বিগুণ fractional Knapsack ( গঠন অবজেক্ট arr [ ] ,
int ভিতরে, int আকার )
{
সাজান ( আরআর, আরআর + আকার, cmp ) ;
int ওজন কম = 0 ;
দ্বিগুণ চূড়ান্ত মান = 0.0 ;
জন্য ( int i = 0 ; i < আকার ; i ++ ) {
যদি ( ওজন কম + arr [ i ] . ওজন <= ভিতরে ) {
ওজন কম + = arr [ i ] . ওজন ;
চূড়ান্ত মান + = arr [ i ] . মান ;
}
অন্য {
int থাকা = ভিতরে - ওজন কম ;
চূড়ান্ত মান + = arr [ i ] . মান
* ( ( দ্বিগুণ ) থাকা
/ arr [ i ] . ওজন ) ;
বিরতি ;
}
}
ফিরে চূড়ান্ত মান ;
}
int ভিতরে = 60 ;
অবজেক্ট arr [ ] = { { 100 , বিশ } ,
{ 380 , 40 } ,
{ 140 , 10 } ,
{ 180 , 30 } } ;
int আকার = আকার ( arr ) / আকার ( arr [ 0 ] ) ;
cout << 'সর্বোচ্চ লাভ ='
<< fractional Knapsack ( arr, v, আকার ) ;
ফিরে 0 ;
}
এই কোডে, একটি বস্তুর কাঠামো সংজ্ঞায়িত করা হয়েছে যার ওজন এবং লাভের মান রয়েছে। bool cmp() দুটি বস্তুর ওজন এবং মূল্যের অনুপাতের ভিত্তিতে দুটি বস্তুর মধ্যে তুলনা করতে ব্যবহৃত হয়। অ্যারেটি নিচের ক্রমানুসারে সাজানো হয় এবং যতক্ষণ না এটি সর্বোচ্চ না পৌঁছায় ততক্ষণ পর্যন্ত মান যোগ করতে থাকে। যদি বর্তমান মান অনুমোদিত হয় এবং সীমার মধ্যে, এটি যোগ করা হয়, অন্যথায় এর হ্রাসকৃত অনুপাত ব্যাগে যোগ করা হয়। ওজন এবং মানের পরিমাণ প্রধান কোডে ইনপুট করা হয় এবং সর্বোচ্চ লাভ আউটপুটে মুদ্রিত হয়।
জলখাবারে সর্বোচ্চ লাভ হল ৫৮০ টাকা।
উপসংহার
C++-এ ভগ্নাংশের ন্যাপস্যাক সমস্যাটি একটি নির্দিষ্ট ওজন এবং লাভের আইটেমগুলি দিয়ে একটি ব্যাগ পূরণ করার একটি উপায় সনাক্ত করাকে বোঝায় যাতে ব্যাগটি সর্বাধিক সীমা অতিক্রম না করে সর্বোচ্চ মান ধারণ করে। এটি লোভী পদ্ধতির দ্বারা অর্জন করা যেতে পারে যার লক্ষ্য প্রতিটি ধাপে আদর্শ পছন্দ করা, যা শেষে আদর্শ সমাধানের দিকে নিয়ে যায়।