ভগ্নাংশ ন্যাপস্যাক সমস্যা

আইটেমের একটি তালিকা দেওয়া হয়েছে, প্রতিটি আইটেমের নিজস্ব মান এবং ওজন রয়েছে৷ আইটেমগুলি একটি ন্যাপস্যাকে রাখা যেতে পারে যার সর্বাধিক ওজনের সীমা W। সমস্যাটি হল W এর কম বা সমান ওজন খুঁজে বের করা এবং মান সর্বাধিক করা হয়।

ন্যাপস্যাক সমস্যা দুই ধরনের।

• 0 – 1 ন্যাপস্যাক
• ভগ্নাংশ ন্যাপস্যাক

0 - 1 ন্যাপস্যাকের জন্য, আইটেমগুলিকে ছোট টুকরোগুলিতে ভাগ করা যায় না, এবং ভগ্নাংশের ন্যাপস্যাকের জন্য, আইটেমগুলিকে ছোট ছোট টুকরোগুলিতে বিভক্ত করা যেতে পারে৷

এখানে আমরা ভগ্নাংশের ন্যাপস্যাক সমস্যা নিয়ে আলোচনা করব।

এই অ্যালগরিদমের সময় জটিলতা হল O(n Log n).

ইনপুট এবং আউটপুট

ইনপুট:সর্বোচ্চ ওজন =50। মান এবং ওজন সহ আইটেমগুলির তালিকা। 30

অ্যালগরিদম

fractionalKnapsack(ওজন, আইটেমলিস্ট, n)

ইনপুট - ন্যাপস্যাকের সর্বোচ্চ ওজন, আইটেমের তালিকা এবং আইটেমের সংখ্যা

আউটপুট: প্রাপ্ত সর্বোচ্চ মান।

মূল্য এবং ওজনের রেশনের উপর ভিত্তি করে আইটেম তালিকা বাছাই শুরু করুন বর্তমান ওজন :=0 knapsackVal :=0 তালিকার সমস্ত আইটেমের জন্য i করি যদি বর্তমান ওজন + আইটেমের ওজন [i] <ওজন তারপর বর্তমান ওজন :=বর্তমান ওজন + ওজন আইটেমের [i] knapsackVal :=knapsackVal + আইটেমের মান [i] বাকি আছে:=ওজন – বর্তমান ওজন knapsackVal “=knapsackVal + আইটেমের মান[i] * (আইটেমের অবশিষ্ট/ওজন[i]) লুপ ভেঙে শেষ করুন 
উদাহরণ
 
#include #include namespace ব্যবহার করে std;struct item { int value, weight;};bool cmp(struct item a, struct item b) { // আইটেম a এবং আইটেম b এর উপর ভিত্তি করে তুলনা করুন মান এবং ওজনের অনুপাত দ্বিগুণ aRatio =(ডবল) a.value / a.weight; দ্বিগুণ অনুপাত =(ডবল) b.value / b.weight; রিটার্ন aRatio> bRatio;}ডাবল fractionalKnapsack(int weight, itemList[], int n) { sort(itemList, itemList + n, cmp); // তুলনা ফাংশন ব্যবহার করে আইটেম তালিকা সাজান int currWeight =0; // ন্যাপস্যাকের বর্তমান ওজন ডাবল ন্যাপস্যাকভ্যাল =0.0; জন্য (int i =0; i  
আউটপুট
 
সর্বোচ্চ মান:240