C++-এ একটি বোর্ডকে বর্গাকারে কাটার ন্যূনতম খরচ

কনসেপ্ট

ধরুন একটি বোর্ডের দৈর্ঘ্য p এবং প্রস্থ q দেওয়া আছে, আমাদের এই বোর্ডকে p*q বর্গাকারে ভাঙতে হবে এমনভাবে যাতে ভাঙার খরচ ন্যূনতম হয়। এই বোর্ডের জন্য, প্রতিটি এজের কাটার খরচ দেওয়া থাকবে। সংক্ষেপে, আমাদের কাটার একটি ক্রম নির্বাচন করতে হবে যাতে খরচ ন্যূনতম হয়।

উদাহরণ

উপরোক্ত বোর্ডের সাপেক্ষে বর্গাকারে কাটার অপ্টিমাল পথ হল -

উপরের ক্ষেত্রে টোটাল মিনিমাম খরচ ৬৫। এটি নিচের ধাপগুলো ইমপ্লিমেন্ট করে হিসাব করা হয়েছে।

Initial Value : Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces
Cost 5 Horizontal cut Cost = 0 + 5*1 = 5
Cost 5 Vertical cut Cost = 5 + 5*2 = 15
Cost 4 Vertical cut Cost = 15 + 4*2 = 23
Cost 3 Horizontal cut Cost = 23 + 3*3 = 32
Cost 3 Vertical cut Cost = 32 + 3*3 = 41
Cost 2 Horizontal cut Cost = 41 + 2*4 = 49
Cost 2 Vertical cut Cost = 49 + 2*4 = 57
Cost 2 Vertical cut Cost = 57 + 2*4 = 65

পদ্ধতি

এই ধরণের সমস্যা greedy approach ব্যবহার করে সমাধান করা যায়। যদি টোটাল খরচ S ধরা হয়, তবে S = b1x1 + b2x2 … + bkxk, যেখানে xi হল নির্দিষ্ট এজ কাটার খরচ এবং bi হল সংশ্লিষ্ট কোএফিশিয়েন্ট। কোএফিশিয়েন্ট bi কাটিং প্রসেসের শেষে edge xi ব্যবহার করে আমরা কতবার কাটা করেছি তার দ্বারা নির্ধারিত হয়।

আমাদের লক্ষ্য করতে হবে যে কোএফিশিয়েন্টগুলোর যোগফল সবসময় কনস্ট্যান্ট, সুতরাং আমরা bi-এর একটি বিতরণ খুঁজে বের করতে চাই যাতে S ন্যূনতম হয়। এটি করার জন্য আমরা সবচেয়ে বেশি খরচवाले এজটিতে যত দ্রুত সম্ভব কাটা করি, যা অপ্টিমাল S-এ নিয়ে যাবে। যদি আমরা একই খরচवाले একাধিক এজ পাই, তবে আমরা उनमें যেকোনো একটি প্রথমে কাটতে পারি।

C++ প্রোগ্রাম

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

উদাহরণ

// C++ program to divide a board into p*q squares
#include 
using namespace std;
int minimumCostOfBreaking(int X1[], int Y1[], int p, int q){
  int res1 = 0;
  sort(X1, X1 + p, greater());
  sort(Y1, Y1 + q, greater());
  int hzntl = 1, vert = 1;
  int i = 0, j = 0;
  while (i < p && j < q){
    if (X1[i] > Y1[j]){
      res1 += X1[i] * vert;
      hzntl++;
      i++;
    }
    else{
      res1 += Y1[j] * hzntl;
      vert++;
      j++;
    }
  }
  int total = 0;
  while (i < p)
    total += X1[i++];
  res1 += total * vert;
  total = 0;
  while (j < q)
    total += Y1[j++];
  res1 += total * hzntl;
  return res1;
}
int main(){
  int p = 6, q = 4;
  int X1[p-1] = {3, 2, 4, 2, 5};
  int Y1[q-1] = {5, 2, 3};
  cout << minimumCostOfBreaking(X1, Y1, p-1, q-1);
  return 0;
}

আউটপুট

65