সমস্যা বিবরণ
L দৈর্ঘ্যের একটি রড দেওয়া আছে, কাজ হল রডটি এমনভাবে কাটা যাতে p, q এবং r দৈর্ঘ্যের সেগমেন্টগুলোর মোট সংখ্যা সর্বাধিক হয়। সেগমেন্টগুলো শুধু p, q, এবং r দৈর্ঘ্যের হতে পারে।
যদি l = 15, p = 2, q = 3 এবং r = 5 হয় তবে আমরা ৭টি সেগমেন্ট বানাতে পারি নিচের মতো:
{2, 2, 2, 2, 2, 2, 3}
অ্যালগরিদম
এই সমস্যা ডাইনামিক প্রোগ্রামিং ব্যবহার করে সমাধান করা যায়:
1. dp[] অ্যারে ০ দিয়ে আরম্ভ করুন। 2. রডের দৈর্ঘ্য পর্যন্ত ইটারেট করুন। প্রতিটি i-তে, p, q এবং r দৈর্ঘ্যের কাট করা সম্ভব হলে করা হয়। 3. ans[i+p] = max(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] হবে ০ যদি i-তম ইন্ডেক্সে কাট সম্ভব না হয়। ans[l] দিবে সর্বোচ্চ কাটের সংখ্যা।
উদাহরণ
#include <bits/stdc++.h>
using namespace 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) continue;
if (i + p <= l) dp[i + p] = max(dp[i + p], dp[i] + 1);
if (i + q <= l) dp[i + q] = max(dp[i + q], dp[i] + 1);
if (i + r <= l) dp[i + r] = max(dp[i + r], dp[i] + 1);
}
return dp[l];
}
int main() {
int l = 15, p = 2, q = 3, r = 5;
cout << "Number of segments = " << getMaximumSegments(l, p, q, r) << endl;
return 0;
}
আউটপুট
Number of segments = 7
