আইডিয়া হল গ্রিডি অ্যাপ্রোচ ফ্র্যাকশন্যাল ন্যাপস্যাক প্রব্লেমের জন্য সেরা সমাধান দেয় সেটি ব্যবহার করা।
চেক করতে একটি নির্দিষ্ট নোড আমাদের একটা बेटার সমাধান দিতে পারে কিনা, আমরা অপ্টিমাল সমাধান (নোড দিয়ে) ক্যালকুলেট করি গ্রিডি অ্যাপ্রোচ ইমপ্লিমেন্ট করে। যদি গ্রিডি অ্যাপ্রোচ দিয়ে ক্যালকুলেট করা সমাধান বেস্ট সো ফার-এর চেয়ে বেশি হয়, তবে আমরা সেই নোড দিয়ে बेटার সমাধান পাব না।
সম্পূর্ণ অ্যালগরিদম নিচে দেওয়া হলো −
সকল আইটেম ভ্যালু পার ইউনিট ওয়েট রেশিও অনুযায়ী ডিক্রিজিং অর্ডারে সর্ট করুন যাতে আপার বাউন্ড ক্যালকুলেট করা যায় গ্রিডি অ্যাপ্রোচ দিয়ে।
ম্যাক্সিমাম প্রফিট ইনিশিয়ালাইজ করুন, যেন maxProfit = 0
একটি খালি কিউ, Q, তৈরি করুন।
ডিসিশন ট্রির একটি ডামি নোড তৈরি করুন এবং Q-তে ইনসার্ট বা ইনকিউ করুন। ডামি নোডের প্রফিট এবং ওয়েট ০।
Q খালি না হওয়া পর্যন্ত নিচের কাজ করুন।
Q থেকে একটি আইটেম এক্সট্রাক্ট করুন। এক্সট্রাক্টেড আইটেম u হোক।
নেক্সট লেভেল নোডের প্রফিট ক্যালকুলেট করুন। যদি প্রফিট maxProfit-র চেয়ে বেশি হয়, তবে maxProfit আপডেট করুন।
নেক্সট লেভেল নোডের বাউন্ড ক্যালকুলেট করুন। যদি বাউন্ড maxProfit-র চেয়ে বেশি হয়, তবে নেক্সট লেভেল নোড Q-তে অ্যাড করুন।
কেস বিবেচনা করুন যখন নেক্সট লেভেল নোড সমাধানের অংশ হিসেবে বিবেচিত নয় এবং লেভেল নেক্সট হিসেবে একটি নোড কিউতে অ্যাড করুন, কিন্তু ওয়েট এবং প্রফিট নেক্সট লেভেল নোড বিবেচনা ছাড়া।
নিচে ইলাস্ট্রেশন দেওয়া হলো −
ইনপুট
// প্রতিটি পেয়রের ফার্স্ট জিনিস আইটেমের ওয়েট
// এবং সেকেন্ড জিনিস আইটেমের ভ্যালু
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
আউটপুট
The maximum possible profit = 235
