গ্রিডি অ্যালগরিদম৫ মিনিট পড়া

ফ্র্যাকশনাল ন্যাপস্যাক বা ভগ্নাংশ ন্যাপস্যাক (Fractional Knapsack)

একটি ব্যাকপ্যাক সোনার ধুলো দিয়ে ভরছেন — প্রতি গ্রামের সর্বোচ্চ মূল্যের বস্তু আগে নিন

time:দ্রুত · $O(n \log n)$space:ন্যূনতম · $O(1)$works because:বস্তুগুলো বিভাজ্য — কোনো অতিরিক্ত ক্ষমতা নষ্ট হয় না

কল্পনা করুন আপনি একজন স্বর্ণ সন্ধানী যার কাছে একটি ব্যাকপ্যাক আছে যা ঠিক ১০ কেজি বহন করতে পারে। আপনি সোনার ধুলো, রুপার গুঁড়ো এবং তামার টুকরো খুঁজে পেয়েছেন। আপনি যেকোনো স্তূপ থেকে যেকোনো পরিমাণ তুলে নিতে পারেন — এমনকি আধা-স্কুপও। আপনি কোন স্তূপ আগে নেবেন?

খুব সহজ: প্রতিটি উপাদানের প্রতি গ্রামের মূল্য হিসেব করুন, তারপর সবচেয়ে মূল্যবানটি আপনার ব্যাগ পূর্ণ হওয়া পর্যন্ত (বা স্তূপ শেষ হওয়া পর্যন্ত) নিতে থাকুন, এবং এরপর পরবর্তী মূল্যবানটিতে যান। যেহেতু আপনি ভগ্নাংশ পরিমাণ নিতে পারেন, তাই আপনার ব্যাগের কোনো জায়গা বা ক্ষমতা নষ্ট হবে না।

এটাই হলো ফ্র্যাকশনাল ন্যাপস্যাক সমস্যা, এবং গ্রিডি (greedy) পদ্ধতি এটি $O(n \log n)$ সময়ে নিখুঁতভাবে সমাধান করে।

অ্যালগরিদম

১. প্রতিটি বস্তুর জন্য এর মূল্য-ওজন অনুপাত (value-to-weight ratio) বের করুন: v_i / w_i।
২. অনুপাত অনুযায়ী বস্তুগুলোকে বড় থেকে ছোট (descending order) ক্রমে সাজান।
৩. গ্রিডি বা লোভী হয়ে ব্যাগ ভর্তি করা শুরু করুন: যদি পুরোটা ব্যাগে ধরে তবে সেটি নিন; যদি না ধরে তবে যতটুকু জায়গা খালি আছে ঠিক ততটুকুই নিন। ব্যাগ পূর্ণ হলে থেমে যান।

এটি কেন সঠিক

আপনার ব্যাগের ক্ষমতার প্রতিটি গ্রাম থেকে যেন সর্বোচ্চ সম্ভাব্য মূল্য পাওয়া যায় তা নিশ্চিত করতে হবে। যদি কখনো দেখেন একটি উচ্চ-অনুপাতের বস্তু তখনও অবশিষ্ট থাকা সত্ত্বেও আপনি আপনার ব্যাগের কোনো গ্রাম নিম্ন-অনুপাতের বস্তু দিয়ে ভরে রেখেছেন, তবে আপনি সেই গ্রামটি পাল্টে আরও বেশি আয় করতে পারতেন। একে বলা হয় এক্সচেঞ্জ আর্গুমেন্ট (exchange argument): নিম্ন-অনুপাতের উপাদানের পরিবর্তে সমপরিমাণ উচ্চ-অনুপাতের উপাদান নিন — এতে মোট মূল্য নিশ্চিতভাবে বাড়বে। সুতরাং, সর্বোচ্চ অনুপাতের ক্রম থেকে বিচ্যুত হওয়ার কোনো সুবিধা নেই।

একটি গুরুত্বপূর্ণ পার্থক্য: 0/1 ন্যাপস্যাক

এখন একই সমস্যার কথা চিন্তা করুন, কিন্তু প্রতিটি উপাদান যদি নিরেট পিণ্ড হিসেবে থাকত — যেখানে হয় পুরোটা নিতে হবে অথবা কিছুই নয়। এটাই হলো 0/1 ন্যাপস্যাক (0/1 Knapsack), এবং এখানে গ্রিডি পদ্ধতি কাজ করে না।

উদাহরণ: ব্যাগের ক্ষমতা ১০ কেজি। বস্তুসমূহ: A (৬ কেজি, ১২$, অনুপাত ২.০), B (৫ কেজি, ১০$, অনুপাত ২.০), C (৪ কেজি, ৮$, অনুপাত ২.০)। গ্রিডি পদ্ধতি (অনুপাত অনুযায়ী) হয়তো প্রথমে A নেবে (৬ কেজি, ১২$), তারপর B আর ব্যাগে ধরবে না (৬+৫=১১>১০), তাই এরপর C নেবে (৬+৪=১০, মোট ২০$)। কিন্তু দেখুন B+C মিলে কিন্তু ৫+৪=৯ কেজি হয় এবং মোট মূল্য হয় ১৮$ — এটি খারাপ। আসলে এখানে গ্রিডি কাজ করে গেছে। অন্য একটি উদাহরণ দেখা যাক: ক্ষমতা W=১০, A=(৬,১০), B=(৫,৯), C=(৫,৯)। অনুপাতসমূহ: ১.৬৭, ১.৮, ১.৮। গ্রিডি প্রথমে B+C নেবে? না — যদি টাই-ব্রেকিং এ ভুল হয় তবে হয়তো এটি প্রথমে A নিতে পারে (১০$, ৬কেজি ব্যবহৃত, ৪কেজি বাকি), তখন B বা C কেউই আর ধরবে না। মোট ১০$। কিন্তু B+C নিলে ১৮$ হতো। গ্রিডি পদ্ধতিতে এখানে ৮$ কম পাওয়া গেল।

যে মুহূর্তে বস্তুগুলো অবিভাজ্য হয়ে যায়, গ্রিডি চয়েস প্রোপার্টি ভেঙে পড়ে। তখন আপনার 2D ডায়নামিক প্রোগ্রামিং প্রয়োজন: dp[i][w] = প্রথম i সংখ্যক বস্তু এবং w ক্ষমতা ব্যবহার করে সর্বোচ্চ কত মান পাওয়া যায়।

দ্রষ্টব্য: ভগ্নাংশ নেওয়ার ক্ষমতাই হলো এখানে মূল শক্তি। আপনার ব্যাকপ্যাকের শেষ এক গ্রামও আপনি বাকি থাকা সেরা উপাদানের ঠিক সমপরিমাণ অংশ দিয়ে পূর্ণ করতে পারেন। এই নিখুঁতভাবে পূর্ণ করার ক্ষমতার কারণেই মূলত গ্রিডি চয়েস প্রোপার্টিটি সঠিক থাকে।

ফ্র্যাকশনাল ন্যাপস্যাক — মূল্য/ওজন অনুপাত অনুযায়ী গ্রিডি

def fractional_knapsack(capacity, items):
    # items: list of (weight, value)
    # Sort by value/weight ratio descending
    items_sorted = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
    total_value = 0.0
    remaining = capacity
    for weight, value in items_sorted:
        if remaining <= 0:
            break
        take = min(weight, remaining)
        total_value += take * (value / weight)
        remaining -= take
    return total_value

# Items: (weight, value)
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
result = fractional_knapsack(capacity, items)
print(f"Max value: {result:.1f}")
# Take all of item 3 (30kg, $120), all of item 2 (20kg, $100),
# Total weight 50kg. Value = $240.