Skip to content
Shameem's Note
Shameem Reza JavaScript, WordPress & SwiftUI
Shameem's Note

JavaScript, WordPress & SwiftUI

BUY ME A COFFEE
  • Home
  • About
  • Now
Shameem's Note

JavaScript, WordPress & SwiftUI

June 25, 2017October 15, 2019

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

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

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

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

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

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

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

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

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

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

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

ITEM WEIGHT VALUE
i1 6 6
i2 10 2
i3 3 1
i4 5 8
i5 1 3
i6 3 5

সমাধানঃ

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

Compute density = (value/weight)

ITEM WEIGHT VALUE DENSITY
i1 6 6 1.000
i2 10 2 0.200
i3 3 1 0.333
i4 5 8 1.600
i5 1 3 3.000
i6 3 5 1.667

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

ITEM WEIGHT VALUE DENSITY
i5 1 3 3.000
i6 3 5 1.667
i4 5 8 1.600
i1 6 6 1.000
i3 3 1 0.333
i2 10 2 0.200

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

ITEM WEIGHT VALUE TOTAL
WEIGHT
BENEFIT

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

ITEM WEIGHT VALUE TOTAL WEIGHT TOTAL BENEFIT
i5 1 3 1.000 3.000
i6 3 5 4.000 8.000
i4 5 8 9.000 16.000
i1 6 6 15.000 22.000
i3 1 0.333 16.000 22.333

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

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

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

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

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

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

Bangla

Post navigation

Previous post
Next post

Woth to read

Bangla বাবল সর্ট অ্যালগরিদম

সর্টিংঃ বাবল সর্ট অ্যালগরিদম

June 21, 2017January 26, 2023

সর্টিং মানেই যে কোন কিছু সাজানো, তা আমরা কম বেশি সবাই জানি। কম্পিউটার সায়েন্সের একটি…

Read More
Bangla সিলেকশন সর্ট

সর্টিংঃ সিলেকশন সর্ট

June 21, 2017November 4, 2021

সর্টিং অ্যালগোরিদমের মুল কাজই হচ্ছে অ্যারেতে থাকা দুটি উপাদানের অবস্থান সোয়াপ(swap) বা বিনিময় করা। সিলেকশন…

Read More
Bangla বাইনারি সার্চ ট্রি

বাইনারি সার্চ ট্রি

June 22, 2017January 26, 2023

বাইনারি সার্চ ট্রি এর প্রতিটি নোডে একটি করে মান থাকে। এখানে মান গুলো এমন ভাবে…

Read More
Shameem Reza

I am the Father of a son, blessed with a pious wife. I am a self-taught iOS developer, SwiftUI Addicted and WordPress Ninja.

Over 80,000+ Readers

Get fresh content from Shameem.

  • Twitter
  • GitHub
  • LinkedIn
SwiftUI
JavaScript
Wordpress
Tips & Tricks

Recommended Resources

WordHero: 50+ AI writing tool to write sales and marketing emails that sell.

Rytr: AI Writing Tool to generate high-quality content.

Wave.video: Live Streaming Studio, Video Editor, Thumbnail Maker, Video Hosting, Video Recording, and Stock Library combined in one platform.

Ocoya: An all-in-one marketing solution that helps you effortlessly create, automate, and manage high-converting campaigns.

Join 3500+ Developers Getting Early Access To My Posts!

I learned these in the past 10 years by building a digital product development agency, and dozens of different web & mobile applications for clients and myself. Sign up to get updates when I write something new. No spam ever.

© 2023 Shameem's Note | Contact - Privacy - Disclosure