ফ্র্যাকশনাল ন্যাপস্যাক সমস্যা (Fractional Knapsack Problem)

ফ্র্যাকশনাল ন্যাপস্যাক সমস্যায় আইটেমের লিস্ট দেওয়া থাকে, প্রতিটির ভ্যালু এবং ওয়েট আছে। ন্যাপস্যাকের ম্যাক্সিমাম ওয়েট লিমিট W। লক্ষ্য: টোটাল ওয়েট ≤ W হয় এমনভাবে ভ্যালু ম্যাক্সিমাইজ করা। ০-১ ন্যাপস্যাকে আইটেম ভাগ করা যায় না, কিন্তু ফ্র্যাকশনালে আইটেম ভাগ করা যায়।

টাইম কমপ্লেক্সিটি: O(n log n)

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

Input: Max weight = 50. Items: {(60,10), (100,20), (120,30)}
Output: Maximum value: 240
        (ওয়েট ২০ এবং ৩০-এর আইটেম নেওয়া হয়, বাকি ১০ অংশ নেওয়া হয়)

অ্যালগরিদম

fractionalKnapsack(weight, itemList, n)
Begin
    itemList-কে value/weight রেশিও অনুযায়ী ডিক্রিজিং অর্ডারে সর্ট করুন
    currentWeight := 0, knapsackVal := 0
    for all items i:
        if currentWeight + item[i].weight <= weight:
            currentWeight += item[i].weight
            knapsackVal += item[i].value
        else:
            remaining = weight - currentWeight
            knapsackVal += item[i].value * (remaining / item[i].weight)
            break
    done
    return knapsackVal
End

C++ উদাহরণ

#include <iostream>
#include <algorithm>
using namespace std;

struct Item { int value, weight; };

bool cmp(Item a, Item b) {
    return (double)a.value/a.weight > (double)b.value/b.weight;
}

double fractionalKnapsack(int W, Item arr[], int n) {
    sort(arr, arr+n, cmp);
    int currW = 0; double val = 0.0;
    for(int i=0; i

Maximum value: 240