ধরুন আমাদের একটি রড আছে যার দৈর্ঘ্য n দেওয়া আছে। আমাদের কাছে একটি তালিকাও রয়েছে, যাতে প্রতিটি আকারের জন্য বিভিন্ন আকার এবং মূল্য রয়েছে। রড কেটে বাজারে বিক্রি করে সর্বোচ্চ দাম বের করতে হয়। বিভিন্ন অবস্থানে কাট করে এবং রড কাটার পরে দাম তুলনা করে সেরা দাম পেতে।
সুতরাং, ইনপুটটি যদি দামের মত হয় =[1, 5, 8, 9, 10, 17, 17, 20], n =8, তাহলে আউটপুট হবে 22, যেমন রডটি দৈর্ঘ্য 2 এবং 6 কাটলে। লাভ হল 5 + 17 =22।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আকারের একটি অ্যারে লাভ সংজ্ঞায়িত করুন:n+1।
-
লাভ[0] :=0
-
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), −
-
maxProfit :=ঋণাত্মক অসীম
-
j শুরু করার জন্য :=0, যখন j
-
maxProfit :=সর্বোচ্চ লাভের সর্বোচ্চ এবং মূল্য[j] + মুনাফা[i − j − 1]
-
-
লাভ[i] :=সর্বোচ্চ লাভ
-
-
রিটার্ন maxProfit
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int max(int a, int b) {
return (a > b)? a : b;
}
int rodCutting(int price[], int 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 << rodCutting(priceList, rodLength);
} ইনপুট
{1, 5, 8, 9, 10, 17, 17, 20}, 8 আউটপুট
22
