রড কাটিং

একটি রড n দৈর্ঘ্যের দেওয়া হয়। আরেকটি টেবিলও প্রদান করা হয়েছে, যাতে প্রতিটি আকারের জন্য বিভিন্ন আকার এবং মূল্য রয়েছে। রড কেটে বাজারে বিক্রি করে সর্বোচ্চ মূল্য নির্ধারণ করুন।

বিভিন্ন পজিশনে কাট করে এবং রড কাটার পর দাম তুলনা করে সেরা দাম পেতে।

দৈর্ঘ্য n সহ একটি সারি কাটার পরে f(n) সর্বোচ্চ সম্ভাব্য মূল্য ফেরত দেবে। আমরা সহজভাবে ফাংশন f(n) এভাবে লিখতে পারি।

f(n) :=মূল্য থেকে সর্বোচ্চ মান

ইনপুট এবং আউটপুট

ইনপুট :

বিভিন্ন দৈর্ঘ্যের দাম, এবং রডের দৈর্ঘ্য। এখানে দৈর্ঘ্য 8.

আউটপুট :

বিক্রির পর সর্বোচ্চ লাভ 22।

2 এবং 6 দৈর্ঘ্যে রড কাটুন। লাভ হল 5 + 17 =22

অ্যালগরিদম

রডকাটিং(মূল্য, n)

ইনপুট: মূল্য তালিকা, তালিকায় বিভিন্ন দামের সংখ্যা।

আউটপুট: রড কেটে সর্বোচ্চ লাভ।

শুরু করুন সাইজ n + 1 লাভ[0] :=0 এর জন্য i :=1 থেকে n, করুন maxProfit :=- ∞ এর জন্য j :=0 থেকে i-1, ডু maxProfit :=maxProfit এর সর্বোচ্চ এবং (মূল্য[j] + মুনাফা[i-j-1]) সম্পন্ন লাভ[i] :=maxProfit সম্পন্ন রিটার্ন maxProfitEnd 
উদাহরণ
 নেমস্পেস std;int max(int ​​a, int b) { রিটার্ন (a> b) ব্যবহার করে 
#include ? a :b;}int rodCutting(int price[], int n) { //n এর দাম এবং দৈর্ঘ্য থেকে, সর্বাধিক লাভ int প্রফিট খুঁজুন [n+1]; লাভ[0] =0; int maxProfit; জন্য (int i =1; i<=n; i++) { maxProfit =INT_MIN; //প্রাথমিকভাবে (int j =0; j  
আউটপুট
 
সর্বোচ্চ মূল্য:22