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

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

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

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

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

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

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

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

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

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

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

সমাধানঃ

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

Compute density = (value/weight)

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

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

| ITEM | WEIGHT | VALUE | TOTAL WEIGHT | BENEFIT | | — | — | — | — | — | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |

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

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

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

benefit = (weight taken) x (total value of the item / total weight of the item)

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

weight taken = 5 x (1/2) = 5/2 (as we are taking 1/2 item)

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

#include <stdio.h>

struct Item {
  char id[5];
  int weight;
  int value;
  float density;
};

void fractionalKnapsack(Item items[], int n, int W);

int main(void) {
  //variables
  int i, j;

  //list items
  Item items[6] = {
    {"i1",  6, 6, 0},
    {"i2", 10, 2, 0},
    {"i3",  3, 1, 0},
    {"i4",  5, 8, 0},
    {"i5",  1, 3, 0},
    {"i6",  3, 5, 0}
  };

  //temp item
  Item temp;

  //number of items
  int n = 6;

  //max weight limit of knapsack
  int W = 16;

  //compute desity = (value/weight)
  for(i = 0; i < n; i++) {
    items[i].density = float(items[i].value) / items[i].weight;
  }

  //sort by density in descending order
  for(i = 1; i < n; i++) {
    for(j = 0; j < n - i; j++) {
      if(items[j+1].density > items[j].density) {
        temp = items[j+1];
        items[j+1] = items[j];
        items[j] = temp;
      }
    }
  }

  fractionalKnapsack(items, n, W);

  return 0;
}

void fractionalKnapsack(Item items[], int n, int W) {
  int i, wt;
  float value;

  float totalWeight = 0, totalBenefit = 0;

  for(i = 0; i < n; i++) {
    if(items[i].weight + totalWeight <= W) {

      totalWeight += items[i].weight;
      totalBenefit += items[i].value;

      printf("Selected Item: %s\tWeight: %d\tValue: %d\tTotal Weight: %f\tTotal Benefit: %f\n", items[i].id, items[i].weight, items[i].value, totalWeight, totalBenefit);

    } else {
      wt = (W - totalWeight);
      value = wt * (float(items[i].value) / items[i].weight);

      totalWeight += wt;
      totalBenefit += value;

      printf("Selected Item: %s\tWeight: %d\tValue: %f\tTotal Weight: %f\tTotal Benefit: %f\n", items[i].id, wt, value, totalWeight, totalBenefit);

      break;
    }
  }

  printf("Total Weight: %f\n", totalWeight);
  printf("Total Benefit: %f\n", totalBenefit);
}

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

Selected Item: i5  Weight: 1  Value: 3        Total Weight: 1.000000  Total Benefit: 3.000000
Selected Item: i6  Weight: 3  Value: 5        Total Weight: 4.000000  Total Benefit: 8.000000
Selected Item: i4  Weight: 5  Value: 8        Total Weight: 9.000000  Total Benefit: 16.000000
Selected Item: i1  Weight: 6  Value: 6        Total Weight: 15.000000  Total Benefit: 22.000000
Selected Item: i3  Weight: 1  Value: 0.333333        Total Weight: 16.000000  Total Benefit: 22.333334

Total Weight: 16.000000
Total Benefit: 22.333334

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