C++ এ p, q এবং r দৈর্ঘ্যের সেগমেন্টের সংখ্যা সর্বাধিক করুন

সমস্যা বিবৃতি

L দৈর্ঘ্যের একটি রড দেওয়া হয়েছে, কাজটি হল রডটিকে এমনভাবে কাটা যাতে p, q এবং r দৈর্ঘ্যের মোট অংশের সংখ্যা সর্বাধিক হয়। বিভাগগুলি শুধুমাত্র p, q, এবং r

দৈর্ঘ্যের হতে পারে

যদি l =15, p =2, q =3 এবং r =5 হয় তাহলে আমরা নিম্নরূপ 7টি সেগমেন্ট তৈরি করতে পারি -

{2, 2, 2, 2, 2, 2, 3}

অ্যালগরিদম

আমরা ডায়নামিক প্রোগ্রামিং ব্যবহার করে এই সমস্যার সমাধান করতে পারি

<পূর্ব>1. 02 এ dp[] অ্যারে শুরু করুন। রডের দৈর্ঘ্য পর্যন্ত পুনরাবৃত্তি করুন। প্রতিটি i এর জন্য, সম্ভব হলে p, q এবং r এর একটি কাটা করা হয়।3। ans[i+p] =সর্বাধিক( ans[i+p], 1 + ans[i]), ans[i+q] =max(ans[i+q], 1 + ans[i]) এবং ans শুরু করুন [i+r] =max(ans[i+r], 1 + ans[i]) সব সম্ভাব্য কাটের জন্য।4। ans[i] হবে 0 যদি i-th সূচকে কাটা সম্ভব না হয়। উত্তর[l] সম্ভাব্য সর্বাধিক সংখ্যক কাট দেবে

উদাহরণ

#include নেমস্পেস ব্যবহার করে std;int getMaximumSegments(int l, int p, int q, int r){ int dp[l + 1]; memset(dp, -1, sizeof(dp)); dp[0] =0; for (int i =0; i <=l; ++i) { if (dp[i] ==-1) { চালিয়ে যান; } যদি (i + p <=l) { dp[i + p] =max(dp[i + p], dp[i] + 1); } যদি (i + q <=l) { dp[i + q] =max(dp[i + q], dp[i] + 1); } যদি (i + r <=l) { dp[i + r] =max(dp[i + r], dp[i] + 1); } } রিটার্ন dp[l];}int main(){ int l =15, p =2, q =3, r =5; cout <<"সেগমেন্টের সংখ্যা =" < আউটপুট
 
 আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট-
 তৈরি করে সেগমেন্টের সংখ্যা =7