ফ্র্যাকশনাল ন্যাপস্যাক সমস্যা

গ্রীড অ্যালগরিদমের জন্য ফ্র্যাকশনাল ন্যাপস্যাক (Fractional Knapsack) খুব পরিচিত একটি সমস্যা। অনেকের কাছে এই অ্যালগরিদম কঠিন মনে হলেও, এটি অনেক সহজ একটি অ্যালগরিদম। এমনকি এর ইমপ্লিমেন্টেশন ও খুব সহজ।

ছোট্ট একটা উদাহরণ দিলেই বুঝতে পারবে। ধরে নাও একটি চোর চুরি করার জন্য একটি মুদি দোকানে ঢুকেছে। সেখানে চাল আছে, ডাল আছে, চিনি, লবণ এরকম অনেক জিনিস আছে। এখন সে মানে চোর তো আর সব জিনিস চুরি করতে পারবে না। কেননা তার কাছে যে থলে আছে তার ধারণক্ষমতা ধরে নিলাম ২০ কেজি। তাহলে সে কিভাবে চুরি করলে সব থেকে বেশি লাভবান হবে?

খুবই সহজ এবং সিম্পল একটি সমস্যা। যে জিনিসের দাম বেশি সেই জিনিস আগে নেওয়া শুরু করবে। যদি দেখে ঐ জিনিস শেষ এবং এখনো থলেতে কিছু জায়গা আছে, তাহলে সে আরেকটি দামি জিনিস নেওয়া শুরু করবে। এরকম করে থলে না ভরা পর্যন্ত, অর্থাৎ থলের ধারণক্ষমতা শেষ না হওয়া পর্যন্ত সে নিতে থাকবে।

এখানে খেয়াল রাখতে হবে, দাম বেশি মানে কিন্তু প্রতি কেজিতে দাম। ধরি চাল আছে ১ কেজি, যার দাম ১০০ টাকা এবং ডাল আছে ৫০০ গ্রাম, কিন্তু এর দাম ৬০ টাকা। এখানে কিন্তু ডাল নেওয়া লাভজনক হবে, কেননা ডালের দাম প্রতি কেজি ১২০ টাকা, যেখানে চালের দাম ১০০ টাকা।

এই সমাধান ঠিক থাকবে যদি তুমি কোন জিনিসের যে কোন পরিমাণ নিতে পারো। তবে সমস্যাটি যদি চাল ডালের দোকানে না হয়ে ইলেকট্রনিক্সের দোকানে হয়, তাহলে তুমি আর এয়াভে সমাধান করতে পারবে না। চোর নিশ্চয় একটি টেলিভিশন ভেঙ্গে তার অর্ধেক চুরি করবে না, তাই না? টেলিভিশিন, ল্যাপটপ বা মোবাইল হোক চোর যাই নিতে চাক না কেন, পুরোটাই নিতে হবে।এক্ষেত্রে কিন্তু আমাদের গ্রীডি পদ্ধতি কাজ করবে না।

একটি উধাহরন দেওয়া যাক, মনে করো ১টি টেলিভিশনের দাম ১৫০০০ টাকা এবং ওজন ১৫ কেজি, দুটি মনিটর আছে যাদের ওজন ১০ কেজি করে এবং প্রতিটির দাম ৯০০০ টাকা। তোমার কাছে ২০ কেজি ধারণক্ষমতার একটি থলে আছে, তাহলে তুমি কি করবে? টেলিভিশন নেওয়া কিন্তু বোকামি হবে, যদিও এর প্রতি কেজির দাম বেশি। তারপরেও একটি টেলিভিশনের থেকে দুটি মনিটর নিলেই বরং লাভ বেশি হবে। সুতরাং এটি ভেবো না যে গ্রীডি পদ্ধতি সব সময় কাজ করবে।

এখানে মনে রাখতে হবে, যদি তুমি জিনিসের “কিছু” অংশ নিতে পারো, তাহলে সে সমস্যাক  বলা হয় ফ্র্যাকশনাল ন্যাপস্যাক (Fractional Knapsack), আর যদি পুরোপুরি নিতে হয়, তাহলে তা হবে ০-১ ন্যাপস্যাক (0-1 Knapsack)।

একটি প্রবলেম এবং তার সমাধানঃ

ধরেনি আমাদের একটি ন্যাপস্যাক আছে, যার ম্যাক্সিমাম ধারণ ক্ষমতা হচ্ছে ১৬। এখন আমাদের টার্গেট হচ্ছে, এই ন্যাপস্যাক কে এমন ভাবে ভরা যেন আমরা সর্বোচ্চটি নিতে পারি সর্বোচ্চ প্রফিটের জন্য।

ধরি যে জিনিস গুলো আছে তার সংখা এবং ওজন নিম্নরুপঃ

ITEMWEIGHTVALUE
i166
i2102
i331
i458
i513
i635

সমাধানঃ

  • প্রতিটি জিনিস বা আইটেমের ভ্যালু বে ক্রুতে হবে ওয়েট অনুসারে, অর্থাৎ ভ্যালু ডেনসিটি।
  • ডিসেন্ডিং অর্ডারে আইটেম গুলোর সর্টিং করতে হবে ভ্যালু ডেনসিটি অনুসারে।
  • একটি আইটেমের যতবেশি সম্ভব নেওয়া যায়, তা নিতে হবে।

Compute density = (value/weight)

ITEMWEIGHTVALUEDENSITY
i1661.000
i21020.200
i3310.333
i4581.600
i5133.000
i6351.667

আইটেম গুলোর ভ্যালু ডেনসিটি অনুসারে ডিসেন্ডিং অনুসারে সাজালে আমাদের টেবল হবে নিম্নরুপঃ

ITEMWEIGHTVALUEDENSITY
i5133.000
i6351.667
i4581.600
i1661.000
i3310.333
i21020.200

এখন আমরা খুব সহজেই ঐ জিনিস গুলো নিতে পারবো, যা নিলে আমরা বেশি লাভবান হবো। তবে এখানেও যদি কনফিউশান থাকে বা ঠিক কিভাবে নিবে বুঝতে না পারো, তবে নিচের ন্যাপস্যাক টেবলের সাহায্য নিতে পারোঃ

ITEMWEIGHTVALUETOTAL
WEIGHT
BENEFIT

এই উদাহরনের ক্ষেত্রে মনে রাখতে হবে যে, আমাদের সর্বোচ্চ আইটেম নিতে হবে, কিন্তু তার ওয়েট যেন ১৬ এর বেশি না হয়। তুমি যদি সব ঠিক মত ক্যালকুলেশন করতে পারো, তাহলে তোমার ফলাফল হবে নিচের মতঃ

ITEMWEIGHTVALUETOTAL WEIGHTTOTAL BENEFIT
i5131.0003.000
i6354.0008.000
i4589.00016.000
i16615.00022.000
i310.33316.00022.333

কিভাবে বেনিফিট ক্যালকুলেট করতে হয়?

যদি আইটেম ভ্যালু থাকে ১০ এবং ওয়েট থাকে ৫, আর তুমি যদি সম্পূর্ণ জিনিসই নিতে চাও, তাহলে বেনিফট হিসাবের পদ্ধতি হবেঃ

আবার তুমি যদি কোন জিনিসের ১/২ নিতে চাও, তাহলে বেনিফিট হিসাব করতে হবেঃ

ইমপ্লিমেন্টেশন দেখলে আরো ভালো করে বুঝতে পারবেঃ

উপরের কোডের আউটপুট আসবেঃ

আশাকরি ফ্র্যাকশনাল ন্যাপস্যাক অ্যালগরিদম নিয়ে তোমার মনে আর কোন প্রশ্ন নেই, যদি থাকে তবে অবশ্যয় জানাবে।

Boost Your Career With My Pro Tips

About the Author: Shameem Reza

Shameem is the founder of Melo Pixels Limited. When he isn't plotting new ways to create awesome WordPress themes & plugins, he writes about startups and marketing.

You May Also Like

Leave a Reply

Your email address will not be published. Required fields are marked *