এই ধারণাটি বাস্তবায়িত করা যে লোভী পদ্ধতি ভগ্নাংশের ন্যাপস্যাক সমস্যার জন্য সর্বোত্তম সমাধান প্রদান করে৷
একটি নির্দিষ্ট নোড আমাদের একটি ভাল সমাধান দিতে পারে কি না তা পরীক্ষা করার জন্য, আমরা লোভী পদ্ধতির প্রয়োগ করে সর্বোত্তম সমাধান (নোডের মাধ্যমে) গণনা করি। যদি লোভী পদ্ধতির দ্বারা গণনা করা সমাধানটি এখন পর্যন্ত সেরা থেকে বেশি হয়, তাহলে আমরা নোডের মাধ্যমে একটি ভাল সমাধান পেতে পারি না।
সম্পূর্ণ অ্যালগরিদম নীচে দেওয়া হল -
-
প্রতি ইউনিট ওজনের মানের অনুপাতের অনুপাতের ক্রমানুসারে সমস্ত আইটেম বাছাই করুন যাতে লোভী দৃষ্টিভঙ্গি বাস্তবায়ন করে একটি উপরের সীমা গণনা করা যায়।
-
সর্বাধিক লাভ শুরু করুন, যেমন maxProfit =0
-
একটি খালি সারি, Q, তৈরি করা হয়েছে৷
৷ -
সিদ্ধান্ত গাছের একটি ডামি নোড তৈরি করা হয় এবং এটিকে Q-তে সন্নিবেশ বা সারিবদ্ধ করা হয়। ডামি নোডের লাভ এবং ওজন 0 হবে।
-
Q খালি বা খালি না থাকা অবস্থায় অনুসরণ করুন৷
-
Q থেকে একটি আইটেম তৈরি করা হয়। এক্সট্র্যাক্ট করা আইটেমটি u হতে দিন।
-
পরবর্তী স্তরের নোডের মুনাফা গণনা করুন। যদি লাভ maxProfit থেকে বেশি হয়, তাহলে maxProfit পরিবর্তন করুন।
-
পরবর্তী স্তরের নোডের সীমা গণনা করুন। যদি বাউন্ড maxProfit এর থেকে বেশি হয়, তাহলে Q.
-তে পরবর্তী লেভেল নোড যোগ করুন -
যখন পরবর্তী স্তরের নোডকে সমাধানের অংশ হিসাবে বিবেচনা করা হয় না বা বিবেচনা করা হয় না তখন বিবেচনা করুন এবং পরবর্তী স্তরের হিসাবে সারিতে একটি নোড যুক্ত করুন, তবে পরবর্তী স্তরের নোডগুলিকে বিবেচনা না করে বা বিবেচনা না করে ওজন এবং লাভ করুন৷
-
নীচে দেওয়া চিত্রগুলি -
ইনপুট
// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
আউটপুট
The maximum possible profit = 235
