একটি দৈর্ঘ্য n এর রড দেওয়া আছে। আরেকটি টেবিলও দেওয়া আছে যেখানে প্রতিটি আকারের জন্য আলাদা মূল্য রয়েছে। রড কাট করে বাজারে বিক্রি করে সর্বোচ্চ লাভ নির্ণয় করতে হবে।
রডের বিভিন্ন অবস্থানে কাট দিয়ে এবং কাটার পর মূল্য তুলনা করে সেরা মূল্য পাওয়া যায়।
f(n) দৈর্ঘ্য n এর রড কাট করে সর্বোচ্চ সম্ভাব্য মূল্য রিটার্ন করবে। আমরা সহজে ফাংশন f(n) এভাবে লিখতে পারি:
f(n) := price[i] + f(n – i – 1) থেকে সর্বোচ্চ মান, যেখানে i হল 0 থেকে (n – 1) পর্যন্ত।
ইনপুট এবং আউটপুট
ইনপুট:
বিভিন্ন দৈর্ঘ্যের মূল্য, এবং রডের দৈর্ঘ্য। এখানে দৈর্ঘ্য ৮।
আউটপুট:
বিক্রি করার পর সর্বোচ্চ লাভ ২২।
রডকে ২ এবং ৬ দৈর্ঘ্যে কাটুন। লাভ ৫ + ১৭ = ২২
অ্যালগরিদম
rodCutting(price, n)
ইনপুট: মূল্য তালিকা, তালিকায় মোট কতটি ভিন্ন মূল্য আছে।
আউটপুট: রড কাট করে সর্বোচ্চ লাভ।
শুরু
profit নামক অ্যারে সংজ্ঞায়িত করুন আকার n + 1
profit[0] := 0
i := 1 থেকে n পর্যন্ত, করুন
maxProfit := - ∞
j := 0 থেকে i-1 পর্যন্ত, করুন
maxProfit := maxProfit এবং (price[j] + profit[i-j-1]) এর মধ্যে সর্বোচ্চ
শেষ
profit[i] := maxProfit
শেষ
maxProfit ফেরত দিন
শেষউদাহরণ
#include <iostream> using namespace std; int max(int a, int b) { return (a > b)? a : b; } int rodCutting(int price[], int n) { //price এবং n দৈর্ঘ্য থেকে সর্বোচ্চ লাভ খুঁজুন int profit[n+1]; profit[0] = 0; int maxProfit; for (int i = 1; i<=n; i++) { maxProfit = INT_MIN; //প্রাথমিকভাবে নেতিবাচক অসীম সেট করুন for (int j = 0; j < i; j++) maxProfit = max(maxProfit, price[j] + profit[i-j-1]); profit[i] = maxProfit; } return maxProfit; } int main() { int priceList[] = {1, 5, 8, 9, 10, 17, 17, 20}; int rodLength = 8; cout << "Maximum Price: "<< rodCutting(priceList, rodLength); }আউটপুট
সর্বোচ্চ মূল্য: ২২
